Problem solving techniques (Example problems) (Cont.)

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)

To know about the fibonacci sequence you may need to read this. To generate this sequence by definition the first two numbers of it is 0, and 1. To get the nth element from fib sequence you just sum the last two elements F(N) = F(N-1)+F(N-2).

Recursive solution

int fib(int n) {
    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;
    }

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