Now that we are introduced to the concept of Dynamic Programming(DP) , let us start doing some real analysis . In this note I am going to conclude 1-D DP .

-----------------------

Let us start of with a problem :

Q. Given a number , find the different number of ways to write this number as the sum of { 1 , 2 , 3 } (say) . --> Say , the given number is 5 . We can represent it as,

5 - 1+1+1+1+1
    1+1+1+2
    1+1+2+1
    1+2+1+1
    2+1+1+1
    1+1+3
    1+3+1
    3+1+1
    2+2+1
    2+1+2
    1+2+2
    2+3
    3+2

The answer is 13 .

Now think for a while how you can solve this problem using DP !!!!!

Sub - problems : Let for n ,

n = 1 , the answer is 1 .
n = 2 , the answer is 2 . ( 1+1 , 2 )
n = 3, the answer is 4. ( 1+1+1 , 1+2 , 2+1  , 3 )

and so on . Let us consider a array D to store all our values

D[k] = 0 , k<1
D[1]=1 , D[2]=2, D[3]=4

We just got our base cases!!!

Recurrences : Consider the recurrence ,

n = x1 + x2 + ... + xn

If xn = 1 , then the rest of the term must add up to n-1 .

In our given problem , the relation would be ,

Dn = Dn-1 + Dn-2 + Dn-3

Now we are done . Try to implement the above details .

Short answer ( :) ) ,

for( int i = 4 ; i<=n ; ++i )
D[i] = D[i-1] + D[i-2] + D[i-3]

For n=5 , D[5]=13 (check)

This problem is a variation of the classical "Coin Change" problem .( See O(n) implementation using 1-D array )

http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

So , we can see that problems involving simple recurrences can be solved using DP with linear time complexity .

Try solving these problems using 1-D DP :

problem 1

problem 2

problem 3

.