Dynamic Programming – From Recursive to Iteration – Using 2D DP array.

Introduction

I have explored various ways to apply Recursive to solve Dynamic Programming. The common technique is to use backtracking. Using recursiveness is more intuitive but:

• it is like brute force, if no memoization is used
• recursive call is expensive and too many calls can cause stack overflow.
• constructing tree and figuring relation between child nodes and parents nodes cumbersome, prone to error, hard to debug. Think of trying to figure out why a node doesn't return expected output after 20 recursive calls.

Therefore, it is often better to solve Dynamic Programming "bottom up", using "iteration". The codes could be cleaner, shorter. Here are a few techniques:

1. Using stack and queue to store nodes that needed to be traversed. This is commonly used in implementing BFS, DFS. The time complexity is O(MxN)
   • Run while loop.
   • Inside perform needed logic, add nodes in, and pop out node when traversing between nodes.
   • Terminate while loop when the stack or queue is empty.
   • Optimize by marking visited node, or provide such logic to distinguish the visited node and don't add them back to stack/queue.
2. Problems similar to Minimum Path in Grid calculates the tree nodes values when iterating over each element on a 2D array. The time complexity is O(MxN).
3. Problems similar to ... 1D array.

In this blog, I discuss a few problems that could make uses of the 2nd techniques.

Problem Minimum Path in Grid

Minimum Path in Grid could be solved by observing that we could create a 2D matrix to update the cost of moving from cell {0,0} to cell {n,n}.

Recursive approach

Using recursive calls, we have to construct a complicating tree like below.

• Each time we move to the next cell, update the cost.
• When backtracking, the cost is returned and added to the parent node.
• Final cost or result is store to cell(0,0).

Thus if we could visualize a matrix to store values on each nodes and how to traverse the grid and calculate the value on each cell, the implementation is much cleaner.

Iteration Approach

The 2D matrix could be visualized as below:

• For the bottom row: dp[row][col] = grid[row][col+1] + dp[row][col+1]
• For the left most column: dp[row][col] = grid[row][col] + dp[row+1][col]
• For other cells: dp[row][col] = min(dp[row+1][col],dp[row][col+1]) + grid[row][col]

Code Implementation:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        for (int row = grid.size()-1; row>=0; row--){
            for(int col = grid[0].size()-1; col>=0; col--){
                cout<<"row "<< row <<" col "<<col<<endl;
                if (row == grid.size()-1 && col == grid[0].size()-1){}
                else if (row == grid.size()-1)
                    grid[row][col] = grid[row][col+1] + grid[row][col];
                else if (col == grid[0].size()-1)
                    grid[row][col] = grid[row+1][col] + grid[row][col];
                else{
                    grid[row][col] = min(grid[row+1][col]+ grid[row][col],
                                        grid[row][col+1]+ grid[row][col]);
                }
            }
        }
        return grid[0][0];
    }
};

Problem Pain Houses

The 3 following problems on Leet Codes well applied 2D matrix to store values. All 3 also derives from the basic Minimum Falling Path Sum problem.

• Paint House - LeetCode: paint n houses with 3 colors
• Paint House II - LeetCode: paint n houses with k colors
• Paint House III - LeetCode: paint n houses with k colors and constrains that certain house should not be repainted.

This blog explains the solution for Paint House 2, as it provides the most general ideas and codes templates that could be reused for any problem variants.

Recursive approach:

If we opt to use Recursive and make a tree to represents all choices, then we have:

Iteration approach

The following illustrates how 2D arrays could update the cost of painting houses.

• The cells are update by traversing "vertically", column by column. for (int col = 0; col < k; col++)
• For each cell in col, the values is from the grid plus the min cost of cells from different collumns, in lower rows: minCost = min(minCost, costCount[row + 1][nextCol]);

Suppose we have the following input:
costs = [[10, 6, 16, 25, 7, 28], [7, 16, 18, 30, 16, 25], [8, 26, 6, 22, 26, 19], [10, 23, 14, 17, 23, 9], [12, 14, 27, 7, 8, 9]]

The cost 2D array is:

If we run iteration loop vertically, and update the matrix to store the min costs of paining houses from top to bottom (house 0 to house n), then the matrix could be updated as:

Code implementation:

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        int n = costs.size();
        if (n == 0) return 0;
        int k = costs[0].size();
        if (k == 0) return 0;

        // n+1 by k vector to store cost calculations
        vector<vector<int>> costCount(n + 1, vector<int>(k, 0));

        for (int row = n - 1; row >= 0; row--) {
            for (int col = 0; col < k; col++) {
                int minCost = INT_MAX;
                for (int nextCol = 0; nextCol < k; nextCol++) {
                    if (nextCol != col) {
                        minCost = min(minCost, costCount[row + 1][nextCol]);
                    }
                }
                costCount[row][col] = costs[row][col] + minCost;
            }
        }

        int res = INT_MAX;
        for (int col = 0; col < k; col++) {
            res = min(res, costCount[0][col]);
        }
        return res;
    }
};

Problem Minimum size subarray sum

The problem Minimum Size Subarray Sum - LeetCode is attempted with Recursive and Iteration approach.

Recursive Approach

Using recursive approach, I would make a decision tree as follow:

1. Base Cases:
   • If sum is greater than or equal to the target, return 0 (indicating the end of the subarray).
   • If index is out of bounds, return INT_MAX - 1 to indicate an invalid subarray.
2. Recursive Calls:
   • pick: Include the current element and move to the next index.
   • noPick: Exclude the current element and move to the next index.
3. Return Value:
   • The minimum of pick and noPick is returned.
   • Adjust the final result to account for the initial call by adding 1.

Code Implementation

class Solution {
    int target_;
    int makeSubArr(vector<int>& nums, int index, int sum) {
        // base cases
        if (sum >= target_)
            return 0;
        if (index >= nums.size())
            return INT_MAX - 1;

        // relation:
        int pick = 1 + makeSubArr(nums, index + 1, sum + nums[index]);
        int noPick = makeSubArr(nums, index + 1, sum);

        return min(pick, noPick);
    }
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        target_ = target;
        int result = makeSubArr(nums, 0, 0);
        return result == INT_MAX - 1 ? 0 : result;
    }
};

The above implementation is not quite correct. It has some issue with out inclusion and exclusion of data is handled, but I leave it as it is.

Iteration Approach

The problem Minimum Size Subarray Sum - LeetCode could be solved using 2D matrix to stores the sum of subarray.

• Subarray sub is generated by adding adjacent cells from column left to column right: matrix[row][col] = matrix[row][col - 1] + nums[row];
• A subarray could be a single item and its sum is just the item; therefore, we have special case: matrix[row][row] = nums[row][row]
• The answer could be easily retrieve by keep tracking of the min size of subarray, which is col-row-1

The following illustrates how the 2D matrix could be filled and returns answer:

• place the input nums on horizontal and vertical axis.
• the green cells indicates the sum of the smallest subarray when each cell is added to the subarray
• the subarray could be 1 cell, thus for special scenario, we have matrix[col][col]= nums[col]
• the sum of the subarray is progressively added from the previous cell on the same row. matrix[row][col] = matrix[row][col - 1] + nums[col];
• minLength is calculated and updated as the 2D array is filled.

Code Implementation:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> matrix(n, vector<int>(n, INT_MAX));
        int minLength = INT_MAX;
        // Fill the matrix with subarray sums
        for (int i = 0; i < n; ++i) {
            matrix[i][i] = nums[i];
            if (matrix[i][i] >= target)
                return 1;
            for (int j = i + 1; j < n; ++j) {
                matrix[i][j] = matrix[i][j - 1] + nums[j];
                if (matrix[i][j] >= target) {
                    minLength = min(minLength, j - i + 1);
                    break;
                }
            }
        }

        return minLength == INT_MAX ? 0 : minLength;
    }
};

The above implementation would cause Memory Limit Exceed for the obvious reason.

• Space Complexity O(n^2)
• Time complexity O(n^2).

The better techniques would be 2 pointers, sliding windows, and will be discussed in a different post.

Problem Maximum Length of Repeated Subarray

Problem description: Maximum Length of Repeated Subarray - LeetCode

Iteration Approach 2D array

The below approach uses 2D array to update the length of common subarray.

• The 2D array is within the black bordered.
• Green cells indicate subarrays where there is/are common cells.
• Continuous subarray has size updated from is previous diagonal adjacent cells.

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int ans = 0;
        for (int row = 0; row < m; ++row) {
            for (int col = 0; col < n; ++col) {
                if ( nums1[row]==nums2[col]){
                    if (row == 0)
                        dp[row][col] = 1;
                    else if (col == 0)
                        dp[row][col] =1;
                    else
                        dp[row][col] = dp[row-1][col-1] + 1; 
                }   
                // else dp[row][col] = 0;
                ans = max(ans, dp[row][col]);
            }
        }
        return ans;
    }
};

Iteration Approach 1D array

From earlier implementation, we see that 2D array wastes space, and the values are not updated unless there are common cells. The following optimized space complexity by using two 1D arrays:

• run nested for loop to compare items between array, where inner loop with column index
• update dp array, dp[col] = dpPre[col-1]+1, otherwise, dp[col]=0
• swap dp and dpPre after each iteration in the inner loop

Space complexity will be O(2*col) where col is the length of the longer nums array.

Code implementation

class Solution { // 272 ms, faster than 48.13%
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if (m < n) return findLength(nums2, nums1); // Make sure len(nums1) > len(nums2) to optimize space
        vector<int> dp(n+1), prevDP(n+1);
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i-1] == nums2[j-1])
                    dp[j] = prevDP[j-1] + 1;
                else dp[j] = 0;
                ans = max(ans, dp[j]);
            }
            dp.swap(prevDP);
        }
        return ans;
    }
};