Part 1 – Dynamic Programming – Topdown vs Bottom Up Approach

Concept

• Dynamic programming divides the original problems into subproblems where the result of previous subproblem affects the results of the next subproblems.
• The subproblem result can be reused multiple times.
• Listing out all the subproblems and result is same as traversing a decision tree where each node is a state. Each branch is the logic the leads to the next problem.
• Each state has state variables or the inputs, parameters of recursive functions, or the values of dynamic make recursive calls according to the recurrence relation whenever the current state is not a base case array dp[].
• Topdown method: make recursive calls according to the recurrence relation whenever the current state is not a base case
• Bottom up: bottom-up DP solutions require us to iterate over the subproblems in a specific order so that all of the results necessary to solve the subproblem for the current state have already been obtained before arriving at the current state
• The following table distinguishes Topdown and Bottom Up approach:

	Topdown	BottomUp
Implementation	Use recursive equation	Use dp equation/array
Optimization	By using memoization/cache	By storing value into array(tabluation)
Complexity	slightly worse than O(n)	O(n)

• For both approaches, the similarity are:
  1. Complexity without optimization is: number of branches at each node * depth of tree
  2. Complexity after Optimization: O(n) because we traverse through a single for loop. (it is best seen in bottom up approaches.)
  3. To change from Topdown to bottom-up solution, we need to find correct order in which to iterate over the states.

• To solve a DP problem, we need 3 things:
  1. Figure out state and state variable. Design a data structure to store the answer for the problem in any given state.
  2. A recurrence relation to transition between states. For top-down approach, the recurrence relation can be expressed as recursive calls. For bottom-up approach, an DP equation is often used.
  3. Base cases.

Sample problems Climbing Stairs

Problem requirements:

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2

• Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3

• Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution 1 Topdown - Brute Force - Decision Tree

Design approach:

• Construct a decision tree (as binary tree) to analyze how many ways we can reach target from 0.
• Could solve problem using DFS. Complexity = O(2^n) where n = heigh of the tree

Data Structure

• set counter += 1 each time we reach the ending step.

Algorithm

• populate the binary tree by recursively calling climbSteps(startingStep, endStep, stepSize)
• DFS implementation: going deeper by setting startingStep = startingStep + stepSize
• traverse every branch of the decision tree by recursively calling climbingStep().
• each time startingStep = endStep: return 1, increment the counter.

#include <iostream>

using namespace std;

// top down solution, brute force, traverse every branch, going deeper first.
// this solution causes Time Limit Exceed
class Solution {
    public:
    int climbStairs(int n) {
        int counter = 0;
        counter += climbStairsRecursive(0,n, 1) + climbStairsRecursive(0,n, 2);
        cout<<"Result: "<<counter<<endl;
        return counter;
    }

    int climbStairsRecursive(int startingStep, int endStep, int stepSize){
        cout<<" -- start "<<startingStep<<" -- end "<<endStep<<" -- stepSize "<<stepSize<<endl;
        startingStep = startingStep + stepSize;
        cout<<"nextstep "<<startingStep<<endl;
        if (startingStep == endStep){
            cout<<"add 1"<<endl;
            return 1;
        }
        else if (startingStep<endStep) {

            return climbStairsRecursive(startingStep, endStep, 1) + climbStairsRecursive(startingStep, endStep, 2);
        }
        else {
            cout<<"not reaching end"<<endl;
            return 0;
        }
    }
};

int main() {
    Solution sol;
    sol.climbStairs(35);
}

Complexity analysis

Complexity = O(2^n) where n = heigh of the tree

Solution 2 Topdown Approach, Memoization

Design Approach

• Construct a decision tree (as binary tree) to analyze how many ways we can reach target from step 0 (Root of tree, Top) to destination (child left of tree, Down)
• Parts of the decision trees are repeated. Thus the problem depends on finding paths from 0, 1, 2, 3, 4,... n ]
• Use Recursive from Top to Bottom, Result are returned from base case at the bottom.

Data Structure

• set counter += 1 each time we reach a destination.
• use vector<int>cache to store the result from earlier subproblem
• the subproblem is the number of ways to reach the endStep from a starting steps.
• cache is saved when cache[startingStep] >1 (there is a result from a starting Step to end step)

Algorithm

• Base cases
  1. return 1 if startingStep = endStep
  2. return 0 if startingStep > endStep
• Recursive cases
  1. if startingStep < endStep
  2. traverse down the decision tree: startingStep = startingStep + stepSize until startingStep = endStep.
  3. make recursive function:

int climbStairs(int startingStep, int endStep, vector<int> &cache)

• memoization:
  1. initialize cache to zero
  2. save the cache[startingStep] = earlier result
  3. retrieve result from cache[startingStep] if cache[startingStep]>0

The following image illustrates the recursive calls through a decision tree. At each node is a recursive call where the parameters startingStep. endingSteps, and cache are input into climbStairs functions

Code

#include <iostream>
#include <vector>
#include <map>

using namespace std;

// top down solution, saving result to cache
class Solution {
    public:
    int climbStairs(int n) {
        vector<int> cache(n,0);
        return climbStairsRecursive(1,n, cache) + climbStairsRecursive(2,n, cache);
    }


    int climbStairsRecursive(int startingStep, int endStep, vector<int> &cache){
        cout<<" -- start "<<startingStep<<" -- end "<<endStep<<endl;

        // base case 1
        if (startingStep == endStep){
            cout<<"add 1"<<endl;
            return 1;
        }
        // recursive case
        else if (startingStep<endStep) {
            if (cache[startingStep] > 0) {       // memoization, return cache
                return cache[startingStep];
            }
            else {
                // memoization, save cache
                cache[startingStep] = climbStairsRecursive(startingStep+1, endStep, cache) + climbStairsRecursive(startingStep+2, endStep, cache);
                //Log
                cout<<"cache["<<startingStep<<"]="<<cache[startingStep]<<" ";
                cout<<endl;
                return cache[startingStep];
            }

        }
        // base case 2
        else {              // case startingStep > endStep
            return 0;
        }
    }
};

int main() {
    Solution sol;
    int result = sol.climbStairs(5);
    cout<<"Result "<<result<<endl;
}

Complexity analysis

Complexity = O(N) where n = heigh of the tree

Solution 3 Bottom Up

• Bottom-up implementations usually use an array, so we will use an array dp[] where dp[i] represents the number of ways to climb to the i_th step
• One can reach n step in one of the two ways:
  1. Taking a single step from (i-1) step
  2. Taking a step of 2 from (i-2) step
     The total number of ways to reach n step is equal to sum of ways of reaching (i-1) step and (i-2) step:
     dp[i] = dp[i-1]+dp[i-2]

Data Structure

• create dp[] to store the number of steps to reach i step

Algorithm

• it is top down approach, which base cases are top cases:
  dp[0]=0
  dp[1]=1
  dp[2]=1

Code

#include <iostream>
#include <vector>
#include <map>

using namespace std;

// Fibonacci approach - DP equations
class Solution {
    public:
    int climbStairs(int n) {
        vector<int> dp(n+1);
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;                    // 2 ways to reach 2nd step: 1 step + 1 step or 2 step
        for (int step = 3; step <=n; step++){
            dp[step]=dp[step-1]+dp[step-2];
        }
        return dp.back();
    }
};

int main() {
    Solution sol;
    int result = sol.climbStairs(5);
    cout<<"Result "<<result<<endl;
}

Complexity analysis

O(n) for both time and space complexity.