Dynamic programming pattern

DP problem at a high level can be solved using the following steps.

1. Define the meaning of the recursion function f(i) .
2. Establish the recursion relationship i.e. how f(i) can be solved based on previously solved 0....i .
3. Compute time complexity

In this post, I will list out patterns that can be used as tools to attempt to solve problems.

Recursion mindset

The recursion approach has two steps to solve the problem.

1. Define the problem unit to make it isolated. For example f(i) is to find out the factorial for ith number it means f(i) here only depends on i .
2. Use previously solved problems to solve new problems. It means if you have already solved 0....i-1 problem then how you can solve f(i) ? For example, f(i)=i*f(i-1) .

We can write factorial recursion code as below.

const recursion = (i)=> {
  // Base case
  if(i == 0) {
    return 1;
  }
  return i * recursion(i-1);
}

Recursion execution tree

It is very important to understand and draw the recursion execution tree. Let’s take an example to solve the Fibonacci number. Here f(i) returns the ith Fibonacci number. We can define the recursion relationship as f(i)=f(i-1)+f(i-2)

Following is the code based on the recursion function.

const recursion = i => {
  // Base case
  if(i < 2) {
    return i;
  }
  return recursion(i-1) + recursion(i-2)
}

Following would be the recursion execution tree for this function.

Once we understand the execution tree then we can find out the following.

1. Time complexity. Here it would be O(2^n) as every parent node starts two child nodes.
2. Repetition of problem. Here you can see f(3) , f(2) etc are repeated multiple times.

Form #1: Recursion concept of level, check, choice, and move

Every recursion problem can be solved using this template. Let’s define this framework.

1. Level: Level is the state of the current problem.
2. Choice: If a person is at the current level i what are the choices a person has?
3. Check: Corresponding to every choice, check if it is a valid move or not.
4. Move: Move defines how to shift from one state to another. You need to explore the choices and come back. I.e. if you are at f(i) how you can move to the next state?

In general, we can use the following template code to apply this pattern.

int recursion(int level) { // This define current level and what it should return
  // Pruning case, this is only applicable if recursion function doesn't check for valid choice
  // base case: solve for zero size problem or simple use case
  
  int ans = 0;
  for (all choices) { // Explore all the choices
    if(check(valid choice)) { // Check validity of choice
      ans = move(choice);    // Move current level to next and update the ans
    }
  }
  return ans;
}

Recursion with Memoization

If you inspect a recursion tree and find that there is repetition in calling the same function with the same state then we can cache the result and reuse it.

We can update our recursion template code as below.

int dp[1000];

int recursion(int level) { // This define current level and what it should return
  // Pruning case, this is only applicable if recursion function doesn't check for valid choice
  // base case: solve for zero size problem or simple use case
  if(dp[level] != -1) { // If cache is already populated then return early
    return dp[level];
  }
  int ans = 0;
  for (all choices) { // Explore all the choices
    if(check(valid choice)) { // Check validity of choice
      ans = move(choice);    // Move current level to next and update the ans
    }
  }
  dp[level] = ans; // Update the cache with answer
  return ans;
}
int solve(int n) {
  memset(dp, -1, sizeof(dp); 
  return recursion(0);
}

This helps to reduce the time complexity of code from exponential to quadratic.

Now let’s solve a few problems using this concept.

Number of ways to climb a staircase

https://leetcode.com/problems/climbing-stairs/description/ (Here change to 3 steps).

To understand this concept, let’s take the staircase problem. How many ways can a person at the level 1 reach to level N ?

Here, a person can either take one step, two steps, or three steps at a time.

Let’s define the concepts.

1. Level: In this problem, the person will be standing on some level of a staircase. If we say f(i) it means the person is at a level i .
2. Choice: In this problem, the person can either take 1 step or 2 steps or 3 steps.
3. Check: Let’s say if person is at f(n-1) step, so it doesn’t make sense for a person to take 2 or 3 steps as it will go out of bounds.
4. Move: I.e. if you are at f(i) how you can move to the next state? f(i)= f(i+1)+ f(i+2) + f(i+3) defines the moves for this problem.

Since f(i) the state is dependent on i only and there is repetition in execution therefore we can also apply the memoization. we can write code as below.

int dp[1000];
int recursion(int i) {
    // Base case: Reach to top
    if(i == n) {
        return 1;
    }
    if(dp[i] != -1) {
      return dp[i];
    }
    int ans = 0;
    // all choices 
    for (int j=1; j <=3; j++) {
        // Check for validity
        if(i + j <= n ) {
            // Move to next state
            ans += recursion(i + j);
        }
    }
    dp[i] = ans;
    return ans;
}
int solve(){
  memset(dp, -1, sizeof(dp));
  reuturn recursion(1);
}

The time complexity of pure recursion: T(3^n)

The time complexity of recursion with memoization : T(n)

N Queens problem

https://leetcode.com/problems/n-queens/description/

For a given n*n chess board, find out how many ways to place n queens on the board so that no queen can attack other queens. A queen can move the same row, same column, and same diagonals.

For 4*4 board with 4 queens, there are 2 ways we can place queens on board.

1. Level: We have two choices to define level here. First, each cell can represent the level. Second, each row represents the level. Since the queen can move horizontally as well therefore it doesn’t make sense to use each cell as a level. Instead, we can use each row as a level. f(i) represents the number of ways to place queen to row i .
2. Choice: We have choices from 0 to col to try to place the queen.
3. Check: We need to check if placing a queen on a given col is a valid choice or not. To do this, we need to store the previously made decision to store the queen. Once we will have previously placed the queen state then only we can verify if the current choice is valid or not. We can introduce an queen array to track the previously taken decisions.
4. Move: I.e. if you are at f(i) how you can move to the next state? f(i)= sum(f(j+1)) where j=0….n-1defines the moves for this problem.

Here state of f(i) not only depends on i but also depends on queen the array. Also, the queen array keeps changing on every i therefore there are no repeatations here.

We can write pure recursion code without memoization as below.

int n;
int queen[]; // Where is queen at row i

boo check(row,col) {
    // Compare with all the previous rows 
    for (int i=0; i < row; i++ ) {
        int j = queen[i]; // previous column for previous row i
        // if same column then we can't place queen 
        if(j == col) {
            return 0;
        }
        // If same diagonal then also can't place the queen 
        if(abs(i-row) == abs(j - col)) {
            return 0;
        }
    }
    return 1;
}

int recursion(int i) { // Number of ways to populate [i,...,n-1] rows for valid configuration
    // Base case: Once reach to the last level 
    if(i == n) {
        return 1;
    }
    int ans = 0;
    // Choices 
    for (int j=0; j < n; j++) {
        // Check if this choice is valid 
        if(check(i,j)) {
            // Place the queen 
            queen[i] = j;
            // Move to next state 
            ans += recursion(i+1);
            // Undo placing the queen  (backtrack)
            queen[i] = -1;
        }
    }
    return ans;
}
int solve() {
    memset(queen, -1, sizeof(queen));
    cout << recursion(0);
}

Time complexity: T(n^n)

Hence, n queen is a backtracking problem, not a DP problem.

No problem is a DP problem unless a constraint is defined which makes it DP.

Maximum skills to gain in a workshop

Similar problem https://atcoder.jp/contests/abc167/tasks/abc167_c

In a workshop, there are N problems to solve. Each problem is represented as (t,s) a pair to represent the time taken to solve the problem is t and skill gains are s . If you have given X as time and K as slots then find out the maximum skills you can gain.

1. Level: Each problem is level here. f(i) defines the gain for the problem from i....n-1 .
2. Choice: For each problem i we have two choices, either choose this problem or skip it.
3. Check: If we are choosing a problem i then we need to make sure the total time doesn’t exceed the given X as well as total slots do not exceed K .
4. Move: I.e. if you are at f(i) i.e. a problem ati then moving next step will be max of both choices. f(i) = max(f(i+1), s + f(i+1))

Based on this, we can first write pure recursion code as below.

int n,x,k;
int t[1000];
int s[1000];
int taken[1000];

bool check(int level) {
    int time_taken = 0;
    int item_taken = 0;
    for (let i=0; i < level; i++) {
        if(taken[i]) {
            time_taken += t[i];
            item_taken += 1;            
        }
    }
    // Now let's take the current item 
    time_taken += t[level];
    item_taken += 1;
    
    // Check for limit 
    if(time_taken <= x && item_taken <= k) {
        return 1;
    }
    reutrn 0;
}

int recursion(int i) { // Max skills I can make from level i to n-1
    // Base case: If we exhausted all levels then no sklls can be again
    if(i == n) {
        return 0;
    }
    // Choices, choose vs skip
    int ans = recursion(i+1); // skip
    // check if choosen choice is valid or not 
    if(check(i)) {
        taken[i] = 1; // Mark it as taken
        ans = max(ans, s[i] + recursion(i+1));
        taken[i] = -1; // Undo it
    }
 
    return ans;
}
int solve() {
    memset(taken, -1, sizeof(taken));
    cout << recursion(0);
}

The time complexity of pure recursion: T(n^n)

Similar to n queen problem, here as well f(i) depends on taken array as dependencies state. Therefore we can’t apply memoization here.

But looking at the check() method carefully, we can actually get rid of the entire taken array and calculate time_taken and item_taken at O(1) . Instead of f(i) , we can define recursion relation based on f(i, time_taken, item_taken) . Then the check condition can be evaluated at O(1) . Now the state of recursion execution is isolated therefore we can apply the memoization. Following is the updated code.

int n,x,k;
int t[1000];
int s[1000];
int dp[1000][1000][1000];

int recursion(int i, int time_taken, int item_taken) { // Max skills I can make from level i to n-1
    // Base case: If we exhausted all levels then no sklls can be again
    if(i == n) {
        return 0;
    }
    if(dp[i][time_taken][item_taken] != -1) {
      return dp[i][time_taken][item_taken];
    }
    // Choices, choose vs skip
    int ans = recursion(i+1); // skip
    // check if choosen choice is valid or not 
    if(time_taken + t[i] <= X && item_taken+1 <= K) { // check in O(1)
        taken[i] = 1; // Mark it as taken
        ans = max(ans, s[i] + recursion(i+1, time_taken + t[i], item_taken+1));
        taken[i] = -1; // Undo it
    }
    dp[i][time_taken][item_taken] = ans;
    return ans;
}
int solve() {
    memset(taken, -1, sizeof(taken));
    cout << recursion(0, 0, 0);
}

The time complexity of recursion with memoization: T(n*X*K)

Don’t write DP code until you calculate the time complexity.

Subset sum target

Find a subset of the target that sums up to the target T . There are N items x0 , x1 , ……, xn-1 with N<=100 and xi < 10^4 .

1. Level: Each number is level here. f(i, t) returns true if numbers are in a rangei, i+1, . . ., n-1 and there is a subset that sums up to t exist.
2. Choice: For each number i we have two choices, either choose this problem or skip it to build the subset.
3. Check: If we are choosing this number i then we need to make sure the total subset sum doesn’t exceed the given T
4. Move: If you are at f(i,t) i.e. a number ati then moving next step will be or of two choices. f(i,t) = f(i+1, t) || f(i+1, t + nums[i])

Since state of f(i,t) is isolated and there is repetition therefore we can apply the memoization to improve the time complexity.

Time complexity: T(n*T) .

int n,T;
int nums[100];
int dp[100][10000];

bool recursion(int i, int total) { // True if subset sum of i...n-1 exist sum with T
    // Base case: if target is reached
    if(total == T) {
        return 1;
    }
    // Base case: Empty list 
    if(i==n) {
        return 0; 
    }
    if(dp[i][total] != -1) {
        return dp[i][total];
    }
    // Choices, choose vs skip
    bool ans = recursion(i+1, total); // skip
    // check if choosen choice is valid or not 
    if(total + nums[i] <=T) {
        ans = ans || recursion(i+1, total + nums[i]);
    }
    dp[i][total] = ans;
    return ans;
}
bool solve() {
    memset(dp, -1, sizeof(dp));
    return recursion(0, 0);
}

Subset sum target Q times

Print all subsets of the target that sum up the target T . There are N items x0 , x1 , ……, xn-1 with N<=100 and xi < 10^4 . There are Q queries.

Q. Can we apply the above code to query Q times?

Ans. No. Bcz recursion(i,total) also depends on external value T to check if total ==T or not.

But if we change the definition of recursion(i, left) then we can change the check left == 0 to make the recursion method independent of external T . Then we can reuse the dp array to query the same method Q times.

Once dp is filled then the time to query will be O(1) . So time complexity of the code would be O(n* max(T))

int n,Q;
int nums[100];
int T[100];
int dp[100][10000];

bool recursion(int i, int left) { // True if subset sum of i...n-1 exist sum with left
    // Base case: if target is reached
    if(left == 0) {
        return 1;
    }
    // Base case: Empty list 
    if(i==n) {
        return 0; 
    }
    if(dp[i][left] != -1) {
        return dp[i][left];
    }
    // Choices, choose vs skip
    bool ans = recursion(i+1, left); // skip
    // check if choosen choice is valid or not 
    if(left - nums[i] >= 0) {
        ans = ans || recursion(i+1, left - nums[i]);
    }
    dp[i][left] = ans;
    return ans;
}
void solve() {
    memset(dp, -1, sizeof(dp));
    for (int i=0; i < Q; i++) {
        cout << recursion(0, T[i]) << endl;
    }
}

Print subset sum target Q times

To print the subset sum, we first run the recursion(i,left) , if it returns the true then run the printset(0,T[0]) .

Following is the updated code with printset() .

int n,Q;
int nums[100];
int T[100];
int dp[100][10000];

bool recursion(int i, int left) { // True if subset sum of i...n-1 exist sum with left
    // Base case: if target is reached
    if(left == 0) {
        return 1;
    }
    // Base case: Empty list 
    if(i==n) {
        return 0; 
    }
    if(dp[i][left] != -1) {
        return dp[i][left];
    }
    // Choices, choose vs skip
    bool ans = recursion(i+1, left); // skip
    // check if choosen choice is valid or not 
    if(left - nums[i] >= 0) {
        ans = ans || recursion(i+1, left - nums[i]);
    }
    dp[i][left] = ans;
    return ans;
}
void printset(int i, int left) {
    // Base case: empty set 
    if(i == n) {
        return;
    }
    // Apply choices
    if(recursion(i+1, left) == 1) { // skip
        printset(i+1, left);
    } else if (left - nums[i] >=0 && recursion(i+1, left - nums[i]) == 1){ // choose
        cout<<" "<< nums[i];
        printset(i+1, left - nums[i]);
    }
}
void solve() {
    memset(dp, -1, sizeof(dp));
    for (int i=0; i < Q; i++) {
        if(recursion(0, T[i]) == 1) {
            printset(0, T[i]);
            cout << endl;
        } else {
            cout <<"No solution found" << endl;
        }
    }
}

Knapsack problem

805. Split Array With Same Average

https://leetcode.com/problems/split-array-with-same-average/description/

You are given an integer array nums.

You should move each element of nums into one of the two arrays A and B such that A and B are non-empty, and average(A) == average(B).

Return true if it is possible to achieve that and false otherwise.

Note that for an array arr, average(arr) is the sum of all the elements of arr over the length of arr.

Example 1:

Input: nums = [1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have an average of 4.5.

Approach 1# Dynamic programming O(n*n*n) — TLE

Let’s understand the goal here.

sum1/n1 = sum2/n2, where n = n1+n2 and sum = sum1+sum2
sum1/n1 = (sum - sum1)/(n-n1)
n*sum1 - n1*sum1 = n1*sum - n1*sum1
n*sum1 = n1*sum
sum1 = n1*sum/n

Here sum and n are constant as we know these value upfront.
sum  = num1+num2+...+numn

So goal here is to build the knapsack with dynamic size n1 with target sum1

We can also write as below
sum1/n1 = sum/n
It means, we just need to find subsequence of target sum/n

So finally our problem is reduced to check each possible length and finding a subsequence of the given array of this length such that the sum of the elements in this is equal to sum1 (which has a logic of 0/1 knapsack).

Following is code which throw TLE.

class Solution {
private:
    bool rec(vector<int>& nums, float target, unordered_map<string, bool>& dp,
             int i, int sum, int size) {
        int n = nums.size();
        float avg = (float)sum / size;
        if (avg == target && size != n) {
            return true;
        }
        if (i == n) {
            return false;
        }
        if (size == n) {
            return false;
        }
        string key = to_string(i)+"-"+to_string(sum)+"-"+to_string(size);
        if (dp.count(key) > 0) {
            return dp[key];
        }
        // choose or skip
        bool skip = rec(nums, target, dp, i + 1, sum, size);
        bool choose = rec(nums, target, dp, i + 1, sum + nums[i], size + 1);

        dp[key] = skip || choose;
        return skip || choose;
    }

public:
    bool splitArraySameAverage(vector<int>& nums) {
        int n = nums.size();
        int sum = reduce(nums.begin(), nums.end());
        float target = (float)sum / n;
        unordered_map<string, bool> dp;
        return rec(nums, target, dp, 0, 0, 0);
    }
};

Form #2: Best ending at index

Let’s learn this form using examples.

Longest increasing subsequence

https://leetcode.com/problems/longest-increasing-subsequence/description/

The goal here is to find out the longest increasing subsequence of the given array [3,2,5,4,5,7,8,1,11,9] .

Using form#1

Technically we can use the Form#1 approach to solve this problem too using the following approach.

1. Level: To check the increasing order, we will need last number in the recursion state. f(i,last) returns the max length of increasing subsequence for i....n-1 and last represents the last number chosen to maintain the increasing order.
2. Choice: For each number i we have two choices, either choose this number or skip it to build the increasing sub-sequence.
3. Check: If we are choosing this number i then we need to make sure that it is greater than the last chosen number.
4. Move: If you are at f(i,last) i.e. a number ati then moving next step will be or of two choices. f(i,last) = max(f(i+1, last), 1+ f(i+1, nums[i])

The time complexity of this DP with memoization will be O(n*max(nums)) . This will result in the time limit being exceeded. Following is the code for reference.

var lengthOfLIS = function(nums) {
    const n = nums.length;
    const dp = new Map();
    const recursion = (i, last) => {
        // Base case
        if(i == n) {
            return 0;
        }
        const key = `${i}-${last}`;
        if(dp.has(key)) {
            return dp.get(key);
        }
        // Try all choices
        let ans = recursion(i+1, last); // skip
        if(nums[i] > last) { // Choose and check the validity
            ans = Math.max(ans, 1+ recursion(i+1, nums[i]));
        }
        dp.set(key, ans);
        return ans;
    }
    return recursion(0, Number.MIN_SAFE_INTEGER);
};

Modification in form# 1

Instead of using last , we can use lastIndex . This will make time complexity more deterministic as O(n*n) . Following is the updated code. But still, this code throws TLE.

var lengthOfLIS = function(nums) {
    const n = nums.length;
    const dp = new Map();
    const recursion = (i, lastIndex) => {
        // Base case
        if(i == n) {
            return 0;
        }
        const key = `${i}-${lastIndex}`;
        if(dp.has(key)) {
            return dp.get(key);
        }
        // Try all choices
        let ans = recursion(i+1, lastIndex); // skip
        if(lastIndex == -1 || nums[i] > nums[lastIndex]) { // Choose and check the validity
            ans = Math.max(ans, 1+ recursion(i+1, i));
        }
        dp.set(key, ans);
        return ans;
    }
    return recursion(0, -1);
};

Using form#2 i.e. best solution ending at i

Now let’s try to solve using form#2. We can define DP as below.

1. Level: f(i) returns the max length of increasing subsequence ending at i i.e on the array of 0.....i .
2. Move: If you are at f(i) i.e. a number ati then for j=0....i-1 , if we have a solution for f(j) and nums[i] > nums[j] then f(i) = 1+ f(j) . To get the best answer, we have to take a max of all these possible answers. We can define transition as f(i)= 1 + max(f(j)) if nums[i] > nums[j] .
3. Ans: Please note f(n-1) is not the answer. f(n-1) only returns the best if you include n-1 as ending number. But the possibility that there is a better answer somewhere in the middle 0....i....n-1 . It means we need to loop again for all i to get the best answer.

We can write recursion with memoization code as below. This code is accepted.

var lengthOfLIS = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(-1);
    const recursion = (i) => {
        if(dp[i] !== -1) {
            return dp[i];
        }
        // compare ith with all previously calculated answer
        let ans = 1;
        for (let j=0; j < i; j++) {
            if(nums[i] >  nums[j]) {
                ans = Math.max(ans, 1 + recursion(j));
            }
        }
        dp[i] = ans;
        return ans;
    }
    // Need to try each number to get the best ans
    let ans = 0;
    for (let i=0; i < n; i++) {
        ans = Math.max(ans, recursion(i));
    }
    return ans;
};

Time complexity: You might be thinking that due to three for loops, now complexity should be (n^3) . But that’s not correct. Here dp plays a role in only running the overall transition in O(n*n) that’s why it is more optimized.

673. Number of Longest Increasing Subsequence

https://leetcode.com/problems/number-of-longest-increasing-subsequence/description

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function (nums) {
    const n = nums.length;
    const dp = new Array(n).fill(-1);
    const count = new Array(n).fill(0);
    const recursion = (i) => {
        if (dp[i] !== -1) {
            return dp[i];
        }
        // compare ith with all previously calculated answer
        let ans = 1;
        count[i] = 1;
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                const local = 1 + recursion(j);
                if (local > ans) {
                    ans = local;
                    count[i] = 0;
                }
                if (ans === local) {
                    count[i] += count[j];
                }
            }
        }
        dp[i] = ans;
        return ans;
    }
    // Need to try each number to get the best ans
    let max = 0;
    for (let i = 0; i < n; i++) {
        max = Math.max(max, recursion(i));
    }
    let ans = 0;
    for (let i = 0; i < n; i++) {
        if (dp[i] === max) {
            ans += count[i];
        }
    }
    return ans;
};

Max sum path on a grid

For a given grid of m*n , find out the max sum path starting from (0,0) and ending to (m-1,n-1) if only downward or right direction is allowed.

Let’s try to use Form#2 to solve this problem.

1. Level: f(i,j) returns the max path sum ending at the cell (i,j) .
2. Move: cell f(i,j) can be either reached from the left or from the top. The transition function can be written as f(i,j) = grid[i][j] + max(f(i,j-1), f(i-1,j)
3. Ans: Since here problem is directly asking to answer to reach the last cell we simply need to return f(m-1, n-1) .

int m,n;
int grid[100][100];
int dp[100][100];
bool done[100][100]; // Since -1 can be a valid answer therefoer need other one

int recursion (int i, int j) { // max path sum ending at i & j cell
    // Base case: Invalid cell return 0
    if(i <0 || i >= m || j < 0 || j >= n) {
        return 0;
    }
    if(done[i][j]) {
        return dp[i][j];
    }
    // To (i,j) we have two ways to reach to this cell, get max from both
    int ans = grid[i][j] +  max(
        recursion(i,j-1), // come from left
        recursion(i-1,j) // come from top
    );
    dp[i][j] = ans;
    done[i][j] = 1;
    return ans;
}

void solve() {
    memset(dp, 0, sizeof(dp));
    memset(done, 0, sizeof(done));
    cout<<recursion(m-1, n-1);
}

Form#3: Multi sequence dp

In this pattern, the problem is given based on multiple sequences. Could be the two arrays of numbers or two arrays of strings. Or could be more than two arrays of any sequence.

This is similar to form#1, i.e. apply valid choices. Let’s try to solve the problem using this approach.

Longest common subsequence of A & B

https://leetcode.com/problems/longest-common-subsequence/

1. Level: f(i,j) returns the max LIS for i...m-1 and j..n-1
2. Choices: To get the longest subsequence, we can skip from string A or from B . If the char is matching then we can skip from both.
3. Move: We can get the maximum answer from all the choices. The transition function can be defined as f(i,j) = max(f(i,j+1), f(i+1,j), A[i]==B[j]?1 + f(i+1,j+1): 0)
4. Time complexity: With memoization, it would be O(m*n)

Following is the code to implement this approach.

const memoization = (text1, text2) => {
    const m = text1.length;
    const n = text2.length;
    const dp = new Array(m).fill(0).map(a => new Array(n).fill(-1));
    const rec = (i, j) => {
        // base case: empty string
        if (i === m || j === n) {
            return 0;
        }
        if(dp[i][j] !== -1) {
           return dp[i][j];
        }
        const ans = Math.max(
            rec(i + 1, j), // skip from text1
            rec(i, j + 1), // skip from text2
            text1[i] === text2[j] ? 1 + rec(i + 1, j + 1) : 0 // choose
        )
        dp[i][j] = ans;
        return ans;
    }
    return rec(0, 0);
}

Form#4: Interval DP

1. Define problem as f(l,r) i.e. to define a subset of the problem.
2. We try to solve f(l,r)

Rod cutting problem

Find out the minimum cost to cut the rod length ninto n-1pieces.

We have the following things to consider.

1. The position to cut the rod matters.
2. The order of the cutting rod also matters.

Let’s apply the DP to solve this problem.

1. Level: f(l,r) returns the minimum cost to cut the rod with (l,r) boundary.
2. Choice: For given l.....p.....r there are p choices to cut the rod.
3. Move: The cost of cutting (l,r) the rod would be cost[r]-cost[l] . Once we choose p then we can define the transition function as f(l,r) = min(ans, cost[r]-cost[l] + f(l,p) + f(p,r))
4. Time complexity: There are total n*n states and in each state, it runs n choices for p so total time complexity will be O(n^3) .

Following is the code to implement memoization.

int n;
int cost[100];
int dp[100][100];

int rec (int l, int r) { // min cost to cut rod between l and r
    // Base case: Single len rod
    if(l + 1 == r ) {
        return 0;
    }
    if(dp[l][r] != -1) {
        return dp[l][r];
    }
    int ans = 1e4;
    for (int p=l+1; p <r; p++) {
        ans = min(ans, cost[r] - cost[l] + rec(l,p) + rec(p,r));
    }
    dp[l][r] = ans;
    return ans;
}

void solve() {
    cost[0] = 0; // Add extra cost in beginning for cost calculation
    memset(dp, -1, sizeof(dp));
    cout<<rec(0, n-1);
}

Form #5: Game dp

Given X chips who will win

• Given x chips in the pool.
• Player can take y chips out of the pool with conditions such as y=2^m .
• The first player who is not able to move loses the game.

int dp[100];

int rec (int x) { 
    // Base case: If no chips, then whoever play will loose
    if(x == 0) {
        return 0;
    }
    if(dp[x] != -1) {
        return dp[x];
    }
    int ans = 0;
    for (int m=0; 1<<m <= x; m++) {
        if(rec(x - (1<< m)) == 0) {
            ans = 1;
            break;
        }
    }
    dp[x] = ans;
    return ans;
}

void solve() {
    memset(dp, -1, sizeof(dp));
    for (int i=0; i < 10; i++) {
        cout << "Player " << i << " "<< rec(i) << endl;
    }
}

Form #6: Multiple players takes same steps

In some of the problems, we can have multiple players and they both traverse at same speed. That leads to a time when they might be in the same cell therefore we might need to take different decision.

741. Cherry Pickup

https://leetcode.com/problems/cherry-pickup/description/

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.

• 0 means the cell is empty, so you can pass through,
• 1 means the cell contains a cherry that you can pick up and pass through, or
• -1 means the cell contains a thorn that blocks your way.

Return the maximum number of cherries you can collect by following the rules below:

• Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1).
• After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells.
• When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0.
• If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.

Greedy approach: doesn’t work

1. Find the most cherries we can pick up with one path, pick them up
2. Find the most cherries we can pick up with a second path on the remaining field.
3. After taking the cherries from that path (and removing them from the grid), we’ll take the cherries again.

Start both from same position on right side

1. Instead of walking from end to beginning, let’s reverse the second leg of the path, so we are only considering two paths from the beginning to the end.
2. Notice after t steps, each position (r, c) we could be, is on the line r + c = t.

3. So if we have two people at positions (r1, c1) and (r2, c2) then after t steps both might be at same r1+c1=t=r2 + c2

Based on this, we can write recursion with memoization as below.

Note: Both players are starting from cell (0,0) .

const recursion = (grid, i,j, k, l, cache) => {
    const n = grid.length; 
    // base case: boundary or block
    if(i ===n || j === n || k === n || l === n || grid[i][j] === -1 || grid[k][l] === -1) {
       return Number.MIN_SAFE_INTEGER; 
    }
    
    // if reach at the end then both will reach at the same time
    if(i === n -1 && j === n -1 && k === n -1 && l === n -1) {
        return grid[i][j];
    }
    
    const key = `${i}-${j}-${k}-${l}`;
    if(cache.has(key)) {
        return cache.get(key);
    }
    
    let currentCherry = 0;
    // if same cell then pick only once (this was the drawback with gridy)
    if(i === k && j === l) {
        currentCherry = grid[i][j];
    } else {
        currentCherry = grid[i][j] + grid[k][l];
    }
    
    const directions = [[1,0],[0, 1]];
    let maxCherry = Number.MIN_SAFE_INTEGER;
    // Apply all four possible directions for both players
    for (const [p, q] of directions) {
        for (const [x, y] of directions) {
            maxCherry = Math.max(
                maxCherry,
                recursion(grid, i+p,j+q, k+x, l+y, cache)
            );            
        }
    }
    
    const total = maxCherry + currentCherry;
    cache.set(key, total);
    return total;
}
/**
 * @param {number[][]} grid
 * @return {number}
 */
var cherryPickup = function(grid) {    
    return Math.max(0, recursion(grid, 0,0,0,0, new Map()));
};

1463. Cherry Pickup II

https://leetcode.com/problems/cherry-pickup-ii/description/

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you:

• Robot #1 is located at the top-left corner (0, 0), and
• Robot #2 is located at the top-right corner (0, cols - 1).

Return the maximum number of cherries collection using both robots by following the rules below:

• From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
• When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
• When both robots stay in the same cell, only one takes the cherries.
• Both robots cannot move outside of the grid at any moment.
• Both robots should reach the bottom row in grid.

Approach

We can simply extend the previous problem as below.

1. Change the second player position to [0,n-1]
2. Since direction can goes to reverse therefore needs to handle negative as edge condition.
3. Due to different starting position, possiblity is that both might reach to the end at different time therefore need to remove this condition too.

Following is same code modified to solve this problem.

const recursion = (grid, i,j, k, l, cache) => {
    const m = grid.length; 
    const n = grid[0].length; 
    // base case: boundary or block
    if(i ===m || j === n || k === m || l === n || i < 0 || j < 0 || k < 0 || l < 0 || grid[i][j] === -1 || grid[k][l] === -1) {
       return 0; 
    }
    
    const key = `${i}-${j}-${k}-${l}`;
    if(cache.has(key)) {
        return cache.get(key);
    }
    
    let currentCherry = 0;
    // if same cell then pick only once (this was the drawback with gridy)
    if(i === k && j === l) {
        currentCherry = grid[i][j];
    } else {
        currentCherry = grid[i][j] + grid[k][l];
    }
    
    const directions = [[1,-1],[1,0],[1,1]];
    let maxCherry = Number.MIN_SAFE_INTEGER;
    // Apply all four possible directions for both players
    for (const [p, q] of directions) {
        for (const [x, y] of directions) {
            maxCherry = Math.max(
                maxCherry,
                recursion(grid, i+p,j+q, k+x, l+y, cache)
            );            
        }
    }
    const total = maxCherry + currentCherry;
    cache.set(key, total);
    return total;
}
/**
 * @param {number[][]} grid
 * @return {number}
 */
var cherryPickup = function(grid) { 
    const m = grid.length;
    const n = grid[0].length;
    return recursion(grid, 0,0, 0, n-1, new Map());
};

Form #7: Multiple scans

542. 01 Matrix

https://leetcode.com/problems/01-matrix/description/

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

Approach #1: Multi source bfs

We can initialize bfs queue with all zeros to find out the shortest path for each one. Following is code for reference.

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> ans(m, vector<int>(n, 0));
        // Initialize queue with all zeros
        queue<vector<int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    q.push({i, j, 0});
                    mat[i][j] = -1; // -1 means already visited
                }
            }
        }
        vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!q.empty()) {
            vector<int> node = q.front();
            q.pop();
            int i = node[0];
            int j = node[1];
            int d = node[2];
            for (vector<int> dir : dirs) {
                int a = dir[0];
                int b = dir[1];
                int x = i + a;
                int y = j + b;
                if (x >= 0 && x < m && y >= 0 && y < n && mat[x][y] == 1) {
                    // Valid neighbor, update ans
                    ans[x][y] = d + 1;
                    q.push({x, y, d + 1});
                    mat[x][y] = -1; // mark as visited
                }
            }
        }
        return ans;
    }
};

Approach #2: Dynamic programming

We can define relationship as below.

f(i,j) = Minimum distance for any zero cell to this cell
f(i,j) = 1 + min(f(i-1,j), f(i+1,j), f(i,j-1), f(i,j+1))

Q. How to scan the matrix for this recursion relationship to maintain the topological sort?

Ans. It is not possible. DP only works with values that have been previously calculated. Here we need both previous and future result.

Q. How to calculate DP then?

Ans. Let’s pretend that we can only move down and right (not allowed to move up and left). That would change the recurrence as below.

f(i,j) = 1 + min(f(i-1,j), f(i,j-1))

Now, let’s pretend that we can only move up and left (not allowed to move down and right). Again, this would change our recurrence as below.

f(i,j) = 1 + min(f(i+1,j), f(i,j+1))

Following is code for reference.

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        vector<vector<int>> dp = mat;
        int m = mat.size();
        int n = mat[0].size();
        // First scan
        for (int i=0; i < m; i++) {
            for (int j=0; j < n; j++) {
                if(dp[i][j] == 0) {
                    continue;
                }
                int count = m * n;
                if(i > 0) {
                    count = min(count, dp[i-1][j]);
                }
                if(j > 0) {
                    count = min(count, dp[i][j-1]);
                }
                dp[i][j] = 1 + count;
            }
        }
        // Second scan
        for(int i=m-1; i >=0; i--) {
            for (int j=n-1; j>=0; j--) {
                if(dp[i][j] == 0) {
                    continue;
                }
                int count = m * n;
                if(i < m-1) {
                    count = min(count, dp[i+1][j]);
                }
                if(j < n-1) {
                    count = min(count, dp[i][j+1]);
                }
                dp[i][j] = min(dp[i][j], 1 + count);
            }
        }
        return dp;
    }
};

Others

493. Reverse Pairs

https://leetcode.com/problems/reverse-pairs/description/

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

Example 1:

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Approach: break down the array and solve for the subproblems

1. let’s assume the input array is nums, with a total of n elements.
2. Let nums[i, j] denote the subarray starting from index i to index j , T(i, j) as the same problem applied to this subarray (for example, for Reverse Pairs, T(i, j) will represent the total number of important reverse pairs for subarray nums[i, j]).

Two ways to build the recursion relationship

1. T(i, j) = T(i, j - 1) + C, i.e., elements will be processed sequentially and C denotes the subproblem for processing the last element of subarray nums[i, j]. We will call this sequential recurrence relation.
2. T(i, j) = T(i, m) + T(m + 1, j) + C where m = (i+j)/2, i.e., subarray nums[i, j] will be further partitioned into two parts and C denotes the subproblem for combining the two parts. We will call this partition recurrence relation.

Approach #1: Sequential recurrence relation

For sequential recurrence relation, we can set i = 0, i.e., the subarray always starts from the beginning. Therefore we end up with:

T(0, j) = T(0, j - 1) + C or in more simplified way can be written as T(j) = T(j - 1) + C

Where the subproblem C now becomes "find the number of important reverse pairs with the first element of the pair coming from subarray nums[0, j - 1] while the second element of the pair being nums[j]

The straightforward way of searching would be a linear scan of the subarray, which runs at the order of O(j). From the sequential recurrence relation, this leads to the naive O(n^2) solution.

To improve the searching efficiency, a key observation is that the order of elements in the subarray does not matter, since we are only interested in the total number of important reverse pairs. This suggests we may sort those elements and do a binary search instead of a plain linear scan.

If the searching space (formed by elements over which the search will be done) is “static” (it does not vary from run to run), placing the elements into an array would be perfect for us to do the binary search.

However, this is not the case here. After the j-th element is processed, we need to add it to the searching space so that it becomes searchable for later elements, which renders the searching space expanding as more and more elements are processed.

Therefore we’d like to strike a balance between searching and insertion operations. This is where data structures like binary search tree (BST) or binary indexed tree (BIT) prevail, which offers relatively fast performance for both operations.

BIT-based solution

const index = (copy, num) => {
    const n = copy.length;
    let left = 0;
    let right = n - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (copy[mid] >= num) {
            // move left
            right = mid - 1;
        } else {
            // move right
            left = mid + 1;
        }
    }
    return left + 1;
}
const search = (bit, i) => {
    let sum = 0;
    while (i < bit.length) {
        sum += bit[i];
        i += i & -i;
    }
    return sum;
}
const insert = (bit, i) => {
    while (i > 0) {
        bit[i]++;
        i -= i & -i;
    }
}
/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function (nums) {
    let ans = 0;
    const copy = [...nums];
    copy.sort((a, b) => a - b);
    const n = nums.length;
    const bit = new Array(n + 1).fill(0);
    for (const num of nums) {
        ans += search(bit, index(copy, 2 * num + 1));
        insert(bit, index(copy, num));
    }
    return ans;
};

II — Partition recurrence relation

For partition recurrence relation, setting i = 0, j = n - 1, m = (n-1)/2, we have:

T(0, n - 1) = T(0, m) + T(m + 1, n - 1) + C

Where the subproblem C now reads "find the number of important reverse pairs with the first element of the pair coming from the left subarray nums[0, m] while the second element of the pair coming from the right subarray nums[m + 1, n - 1]".

Again for this subproblem, the first of the two aforementioned conditions is met automatically. As for the second condition, we have as usual this plain linear scan algorithm, applied for each element in the left (or right) subarray. This, to no surprise, leads to the O(n^2) naive solution.

Fortunately the observation holds true here that the order of elements in the left or right subarray does not matter, which prompts sorting of elements in both subarrays. With both subarrays sorted, the number of important reverse pairs can be found in linear time by employing the so-called two-pointer technique: one pointing to elements in the left subarray while the other to those in the right subarray and both pointers will go only in one direction due to the ordering of the elements.

The last question is which algorithm is best here to sort the subarrays. Since we need to partition the array into halves anyway, it is most natural to adapt it into a Merge-sort. Another point in favor of Merge-sort is that the searching process above can be embedded seamlessly into its merging stage.

So here is the Merge-sort-based solution, where the function "reversePairsSub" will return the total number of important reverse pairs within subarray nums[l, r]. The two-pointer searching process is represented by the nested while loop involving variable p, while the rest is the standard merging algorithm.

Following is code for reference.

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function (nums) {
    const n = nums.length;
    const mergeSort = (start, end) => {
        if (start >= end) {
            return 0;
        }
        const mid = start + Math.floor((end - start) / 2);
        let count = mergeSort(start, mid) + mergeSort(mid + 1, end);
        // ith num in [start, mid] and jth in [mid+1, end]
        let i = start;
        let j = mid + 1;
        while (i <= mid) {
            while (j <= end && nums[i] > 2 * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
            i++;
        }
        // sort
        merge(start, mid, end);
        return count;
    }
    const merge = (start, mid, end) => {
        const temp = [];
        let left = start;
        let right = mid + 1;
        while (left <= mid && right <= end) {
            if (nums[left] <= nums[right]) {
                temp.push(nums[left++]);
            } else {
                temp.push(nums[right++]);
            }
        }
        // copy leftover left
        while (left <= mid) {
            temp.push(nums[left++]);
        }
        // copy leftover right
        while (right <= end) {
            temp.push(nums[right++]);
        }
        // copy into original arr
        for (let i = 0; i < temp.length; i++) {
            nums[start + i] = temp[i];
        }
    }
    return mergeSort(0, n - 1);
};

This post is based on the DP course available at https://maang.in/.