Memoization with recursion, top-down approach + Dynamic Programming, bottom-up


  • 15
    V

    This problem is nothing but a Fibonacci Sequence.

    Let’s define a function T(n) for the number of choices available with n stairs(n steps).There are 2 choices for the first step: One choice is to climb only one stair, and has T(n-1) choices for the remaining n-1 stairs. The other one is to jump two stairs at the first step, and has T(n-2) choices for the remaining n-2 stairs. Therefore, the total number of choices for n stairs is T(n) = T(n-1) + T(n- 2), which is the nothing but Fibonacci Sequence.

    For example, there are three choices to climb up a stair with three levels: (1) climb in three steps, one stair for each climb; (2) climb in two steps, one level for the first step and two levels for the second; or (3) climb with two steps, two levels for the first step and one level for the last jump.

    Now if we code a recursive function T(n) = T(n-1) + T(n-2), each recursive call is called twice for large n, making 2^n calls. This is not recommended. Instead, we save result from each call and check if its available before triggering another call.

    This type of saving the intermediate results to get final result is called Memoization. Here we follow top-down approach.

    int f(int n, int *arr)
    {
    	if (n == 0 || n == 1) return 1;
    	if (arr[n] != 0) return arr[n];
    	else{
    	  arr[n] = f(n - 1, arr) + f(n - 2, arr);
    	  return arr[n];
    	}
    }
    
    int climbStairs(int n) {
    	int *p = (int *)malloc(sizeof(int) * (n + 1));
    	int res, i;
    	
    	if (n == 0 || n == 1) p[n] = 1;  //Base condition
    	
    	for (i = 2; i <= n; i++) p[i] = 0; //For memoization, defaulting all values to 0
    	
    	res = f(n, p);
    	free(p);
    	
    	return res;
    }
    

    Now this even can be simplified, what we call as 'Dynamic Programming'. Instead of going from top down, we will do bottom up approach. Calculate T(n) for small values and build larger values using them.
    The code looks something like this...

    ....
    store[0] = 1;
    store[1] = 1;
    for (i = 2; i <=n; i++)
        store[i] = store[i - 1] + store[i - 2];
    return store[n];
    ...

  • 1
    J

    from my understanding, both bottom up and top down are dp


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.