Java Reference

In-Depth Information

f(5)

f(4)

f(3)

f(3)

f(2)

f(2) f(1)

f(2) f(1)

FIGURE 14.1:
Example of computing the fifth Fibonacci number recursively.

14.2 Dynamic Programming

The king liked the program and tried to run it on his brand-new supercomputer. To

his amazement, the program never gave him an answer. He waited and waited, but the

program never terminated. The king became worried. Had he failed to add a base case and

inadvertently made the program run forever? Careful consideration shows that this is not

the case. The problem is that the program is too slow and runs in exponential time. It

performs the same computations multiple times and is not feasible for larger input.

Having seen Figure 14.1, the king decided that a different approach was in order. How

can the program avoid making the same computations over and over again? The easiest

way is to save the result once it is computed. The program can save the result for
f(0)
,

f(1)
,
f(2)
, and so on. In other words, a bottom-up approach may be called for (instead of

the top-down approach of recursion). Here is the new program that the king wrote.

public class
Test
{

public static void
main(String args [])

{

long
sum = 0L ;

for
(
int
i=1;i
<
= 64; i++)
{

sum = sum + f ( i ) ;

System. out . println (sum) ;

}

public static long
f(
int
day)

{

if
(day == 1)

{

return
1L;

if
(day == 2)

{

return
1L;

long
a[] =
new long
[day + 1];

a[1] = 1L;

a[2] = 1L;

for
(
int
i=3;i
<
= day ;

i ++)

{

a[i] =a[i
−
1] + a[ i
−
2];

return
a[day];

}

}