Basics & 1D DP

Basics

DP is nothing but recursion optimized with storing results of subproblems:

  • Top-down (Memoization)
  • Bottom-up (Tabulation)
  • Iterative (store only last n elements)

DP problems can be iteratively written to optimize space.

Identify if a problem can be solved by DP (naive intuition):

  • calculate all ways
  • calculate “optimal” way (min/max)

Identify if a problem can be solved by DP:

  1. has overlapping subproblems
  2. has an optimal substructure
  3. come up with a state transtion equation

Optimal Substructure: a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This may sound obvious but a lot of times this is not the case.

Ex - in an exam, scoring max in each subject will maximize the overall score but not if score of Maths and English are dependent on each other, if that’s the case then individual scores of Maths and English can’t be optimal at the same time.

DP Demo using Fibonacci

Fibonacci problem is good to set templates for DP, but:

  • ✅ overlapping subproblems
  • ❌ optimal substructure doesn’t matter in this problem (as we’re brute forcing all ways, not finding optimal)
  • ✅ state transition equation (recurrence relation)

Recursive (Brute Force): TC = SC (function call stack) = O(2^n) (exponential)

int fib(int n){
    if(n == 0) return 0;
    if(n == 1) return 1;

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

Notice that the Fibonacci recusrive call tree is an asymmetric tree and its a Complete Binary Tree:

Top-Down (Memoization): TC = SC = O(n)

vector<int> dp(n + 1, -1);		// memo

int fib(int n) {
    if (dp[n] != -1) return dp[n];	// check if available in memo

    // usual base cases
    if (n == 0) return 0;
    if (n == 1) return 1;

    return dp[n] = fib(n - 1) + fib(n - 2);		// store in memo; memoize
}

Function recursion call tree is traversed from top to bottom linearly since we skip further traversal on already stored nodes (calls):

Bottom-Up (Tabulation): TC = SC = O(n)

vector<int> dp(n + 1, -1);

int fib(int n) {
    dp[0] = 0;
    dp[1] = 1;

    for(int i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2];	// only array operations here
    }

    return dp[n];
}

Bottom-Up (Space Optimized): TC = O(n), SC = O(1) (need to store only last two elements)

int fib(int n) {
    int prev2 = 0;
    int prev1 = 1;

    for(int i = 2; i <= n; i++){
        int curr = prev2 + prev1;
        prev2 = prev1;		// sliding
        prev1 = curr;
    }

    return prev1;
}

Calculating TC

TC = work per subproblem * number of subproblems
=> addition of two numbers * n
=> O(1) * O(n)
=> O(n)

If we use a C++ map<int, int> dp (Red-Black Tree) to store instead of an Array, then TC will be O(n * log n) since each operation on such a Tree takes O(log n) time.

DP vs Greedy

Greedy may not work everytime since in order to optimize by choosing minimum at each step, we may miss out on a future shorter path.

Optimal path in the below case (Frog Jump) can be reached only by trying out all choices for each state.

30, 10, 60, 10, 60, 50

Greedy  - 20 + 0 + 40 = 60
Optimal - 30 + 0 + 10 = 40

Greedy chooses the local optimal choice at each step in the hope that it will lead to a global optimum. We travel from left to right in the array and don’t consider all the steps that can be taken from that state but just focus on next best move. It is usually faster than DP.

DP breaks the problem down into smaller subproblems, solves each subproblem just once, stores their results in a table (usually an array or a matrix), and uses these results to construct the solution to larger subproblems. We travel from right to left in the array focusing on solving for current state using smaller (leftwards) state results for all combinations of steps till the current state. It’s often more complex and requires more computational resources than a greedy algorithm.

DP guarantees optimal outcome because of the way its designed. Greedy can make no such guarantees.

1D DP

  1. LC - Climbing Stairs
  2. LC - Min Cost Climbing Stairs

Min cost climbing stairs problem threw me off since we can start at either step 0 or 1, and final step n isn’t given so we can’t call solve(n), only step costs are given. Some observations:

  • cost[i] is the cost if we’re at ith step, destination is nth step and we don’t have any cost for it, this means that we can directly jump from n-1th or n-2th step to nth step without any cost. So for this problem min(solve(n-1), solve(n-2)) will be the ans instead of the usual solve(n)
  • base cases become n = 0, cost[0], and n = 1, cost[1] too since we just need cost[1] to reach 1 (as we can start from 1 at cost cost[1] without any prior steps)

State awareness is really important! Know what states are possible (especially base cases) and what do they return. To ease the identification think about what does a state mean in the problem and what are the bounds.

Identification of state in climbing stair problem: each state represents number of ways to reach that state from step 0

  • recurrence relation dp[i] = dp[i-1] + dp[i-2] means that from i-1th stair to ith stair no. of ways don’t change since we just jump one step (of length 1 stair) so no additional “ways” exists if we just take steps of length 1 in between i-1th and ith step, same applies for i-2th stair and we jump one step (of length 2 stairs) to reach ith step, so to reach ith step we just need to sum them both
  • this pattern of summing all choices is a common pattern for DP problems to count total ways to reach a state (above point explains reason behind it)

Identification of state in min cost climbing stair problem:

  • base case if(n == 0) return 1 means that in order to reach stair 0 (we’re already at it), there is only 1 way (helps in counting with recursion)
  • case if(n < 0) return 0 represents anything less than stair 0 is invalid so return 0 (pruning after recursive call)
  • if we’re pruning with case if(n == 1) return 1, it means that in order to reach stair 1, there is only 1 way (by taking 1 step from stair 0) (pruning before the recusive call; alt way to the above point)
  • min cost climbing stair problem bounds were (0 or 1) to (n-1 or n-2) and not the usual 0 to n since cost was given at each step and not calc between steps
  1. TUF - Frog Jump with k steps
  • optimal solution to this will require atleast k variables (use array of size k), in the worse case i.e. k = n optimal appoach will only be as good as Tabulation (BU)
// use a for loop for each state to do k steps recursion calls
int solve(int i, vector<int>& height, int k) {
    // base case
    if (i == 0) return 0;
    
    int minSteps = INT_MAX;
    
    // loop to try all possible jumps from [1 to k]
    for (int j = 1; j <= k; j++) {
        // don't jump beyond the beginning of the array
        if (i - j >= 0) {
            int jump = solve(i - j, height, k) + abs(height[i] - height[i - j]);
            minSteps = min(minSteps, jump);
        }
    }

    return minSteps;
}

  1. LC - House Robber aka Max Sum of Non-Adjacent Elements - base case dp[0] = arr[0] (since at 0 index max will return dp[0] even if we let the function body run as a result of the pick call; alternatively we can also understand this as - the robber robs the only house if there is a single house with loot amount as dp[0]), state to be pick (p = arr[i] + dp[i - 2]) and not pick (np = 0 + dp[i - 1]), then choose max(p, np) and return it, initial call is solve(n-1) (obvious)

  2. LC - House Robber II - the houses are circular now, no need to think of mod % or anything else here. Smart approach is to observe that arr[n-1] and arr[0] are never part of the total sum simultaneously in a valid solution. Therefore calc but skip element at 0 (= sol1) and calc again skipping element at n - 1 (= sol2), the final answer is max(sol1, sol2)

  3. LC - Counting Bits - base case dp[0] = 0, recurrence dp[i] = dp[i/2] + i%2 (explained in Bitwise algorithms section)

  4. LC - Perfect Squares - base case dp[0] = 0, recurrence min(dp[i], dp[i - j*j] + 1) and we do a for loop to try for all j*j between 1 to sqrt(i). A state here represents “minimum no. of squares needed to sum to i”, and previous state and current state requires 1 more square addition to sum so we add + 1, and we only keep minimum among all previous states