In this post i will show how to use Dynamic Programming technique to solve and optimize your algorithms, you may need to read my previous posts about problem solving techniques.

**Problem 6 (Fibonacci Sequence)**

**Recursive solution**

if(n == 0) return 0;

else if(n == 1) return 1;

return fib(n-1)+fib(n-2);

}

If you draw the call graph for fib(6), it will look like the following:

As you may check each call makes 2 calls for fib(N-1) and fib(N-2). As per the drawing all black nodes are all repeated calls and no need to be called again.

Here we can use dynamic programming to save these repeated calls.

**Memoization Solution using DP**

int memo[10]; // in your main memo[0] = 0, memo[1] = 1

int fib(int n) {

if(memo[n] != -1) return memo[n];

return (memo[n]=fib(n-1)+fib(n-2));

}

Now the call graph for this version is:

As you can see the tree is much smaller than before, and all the dashed nodes are a previously visited state. This code is linear O(N).

**Problem 7 (**

**Changing Sounds**

**)**

Topcoder SRM 366 DIV 1 Level 1

You are a guitar player and you are going to play a concert. You
don't like to play all the songs at the same volume, so you decide to
change the volume level of your guitar before each new song. Before the
concert begins, you make a list of the number of intervals you will be
changing your volume level by before each song. For each volume change,
you will decide whether to add that number of intervals to the volume,
or substract it.

You are given a int[]

**changeIntervals**, the i-th element of which is the number of intervals you will change your volume by before the i-th song. You are also given an int**beginLevel**, the initial volume of your guitar, and an int**maxLevel**, the highest volume setting of your guitar. You cannot change the volume of your guitar to a level above**maxLevel**or below 0 (but exactly 0 is no problem). Return the maximum volume you can use to play the last song. If there is no way to go through the list without exceeding**maxLevel**or going below 0, return -1.
At each song we can generate our current state from the last song satates, checking if each state is a valid state or not. At the last song we can check the max level we can reach returning it, or -1 in case we can reach a level between 0 and max.

**Dynamic programming solution**

int maxFinal(vector <int> intervals, int begin, int max)

{

bool canHave[intervals.size()+1][max+1];

memset(canHave, false, sizeof(canHave));

canHave[0][begin] = true;

int i;

for(i = 0; i < intervals.size(); i++)

{

for(int j = 0; j <= max; j++)

{

if(canHave[i][j])

{

if(j+intervals[i] <= max)

canHave[i+1][j+intervals[i]] = true;

if(j-intervals[i] >= 0)

canHave[i+1][j-intervals[i]] = true;

}

}

}

int res = -1;

for(i = 0; i <= max; i++)

if(canHave[intervals.size()][i] && i > res) res = i;

return res;

}

{

bool canHave[intervals.size()+1][max+1];

memset(canHave, false, sizeof(canHave));

canHave[0][begin] = true;

int i;

for(i = 0; i < intervals.size(); i++)

{

for(int j = 0; j <= max; j++)

{

if(canHave[i][j])

{

if(j+intervals[i] <= max)

canHave[i+1][j+intervals[i]] = true;

if(j-intervals[i] >= 0)

canHave[i+1][j-intervals[i]] = true;

}

}

}

int res = -1;

for(i = 0; i <= max; i++)

if(canHave[intervals.size()][i] && i > res) res = i;

return res;

}

In the next post i will show sample problems solved using greedy technique.

## No comments:

## Post a Comment