Dynamic Programming – From Recursive to Iteration – Solution with 1D Matrix

Introduction

From earlier blog, I approach solving DP problems using iteration technique around 2D matrix, which updates asked values. Using 2D Matrix is costly, thus it is better to use 1D matrix. There are several techniques to come up with a 1D Matrix:

Applying Prefix Sum concept.
Iteration technique with 1D array, applying bottom up or top down analysis.
Using two or more 1D arrays to optimized space.

Notes: 2D matrix or 1D matrix could only be used if the question askes for simple data type. If the question askes for complex data type such as a pair, a list, the techniques are not suitable. Recursive techniques are.

Concept

Iterations:

For me, the problem with recursive solution is that it is hard to debug. In order to debug the issue, I have to print log at every node, after the recursive call returns results. Iteration which makes use of 1D array or 2D arrays provides easier debug if breakpoint is put at near the program termination, where the matrix is fully updated. On performance concern, recursive calls also take up stack space and is inefficient.

Bottom up vs Top down.

Topdown refers to:

set base case at the leaf nodes.
child node return values, and parent nodes are calculated from child nodes.
root node or dp[0][0], also the top left cell stores the final answer.
mostly used with recursive techniques as the recursive call goes deeper to child nodes. After the recursive call returns values, the values is used to calculate parent node value.

Bottom up refers to:

set base case at root node.
mostly used with iteration, where for loop runs from i=0 to end. where i corresponds to a level in decision tree.
the result is usually stored at the rightmost bottom child node.

That I how I user the terms "Bottom-up" vs "Top-down". I see that some may interpret the terms in opposite ways. Thus I think Recursive and Iteration are more acceptable terms and I will use it through out this and other blogs.

0/1 Knapsack problem

0/1 Knapsack problem is described here. In this section, I first solve the problem with recursive solution using a decision tree. Then I change the decision tree a bit and solve the problem using 2D and 1D array. It is concluded that a good decision tree could help with iteration implementation better.

Recursive solution

I made a decision tree as follow:

each node has 2 state variables: profit and weight.
each node has value which is profit and accumulated profit calculated from child nodes.
each node has 2 branches pickItem and noPickItem, the accumulated profit is the max of the two.
base case is reached if there is no more item to pick or the accumulated weight is larger than capacity.
create a memo array to store values of each state. Row index is item index. However, col index should be the accumulated weight

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int pick(int capacity, vector<int>& weight, vector<int>& profit, int itemIndex, int accWeight, vector<vector<int>>& memo) {
    if (itemIndex >= weight.size() || accWeight > capacity) {
        return 0;
    }

    if (memo[itemIndex][accWeight] != -1) {
        return memo[itemIndex][accWeight];
    }

    int pickItem = 0, noPickItem = 0;

    // Pick the item
    if (accWeight + weight[itemIndex] <= capacity) {
        pickItem = profit[itemIndex] + pick(capacity, weight, profit, itemIndex + 1, accWeight + weight[itemIndex], memo);
    }

    // Don't pick the item
    noPickItem = pick(capacity, weight, profit, itemIndex + 1, accWeight, memo);
    memo[itemIndex][accWeight] = max(pickItem, noPickItem);
    return memo[itemIndex][accWeight];
}

int knapSack(int capacity, vector<int>& weight, vector<int>& profit) {
    vector<vector<int>> memo(weight.size(), vector<int>(capacity + 1, -1));
    return pick(capacity, weight, profit, 0, 0, memo);
}

int main() {
    vector<int> profit = { 60, 100, 120 };
    vector<int> weight = { 10, 20, 30 };
    int W = 30;

    int ans = knapSack(W, weight, profit);
    cout << "result " << ans << endl;
    return 0;
}

The following illustrate a decision tree from the above set of inputs:

Iterative solution 2D array

The above problem is called Topdown as the recursive call traverse downward to child nodes, leaf nodes, and returns answer the parent nodes. The root node, also dp[0][0], provides final answer.

Take a look at how the memo array is filled by the end of program:

The above array is hard to follow, but we could change it to bottom up; it would be more intuitive as well!!!

col index is still defined by capacity. Row index is defined by itemIndex+1.
- add a row index=0, represents no item is picked. It is needed for calculations.
for each cell, we have 2 choices:
- don't pick the item because weight is larger than capacity: accumulated profit is dp[row-1][col]. It means the weight has not changed (col is the same), the profit is accumulated profit previously.
- pick the item: still have to compare choice of picking or not picking item, and choose higher return profit.
  - if we picked item and previous item within capacity: profit[itemIndex] + dp[row][capacity - weight[itemIndex]
  - if we only picked this item: profit[row]
the final result is stored at rightmost cell.

For sample input weight = [10,20,30] and values = [60,100,120], Knapsack 2DP array looks like below:

add a row index=0, represents no item is picked. It is needed for calculations.
- Row index =1 corresponds to itemIndex=0
for capacity 20 to 29, we pick itemIndex=2(weight=20) because it gives max profit:
- profit = max(100 + 0, 60) = 100 = dp[1,20] = max(profit[1-1] , dp[1-1][20-20])
for capacity 30, we could pick itemIndex = 2 (weight=20) or itemIndex=0 and itemIndex=1 (accWeight=10+20)

To sum up, iterative solution could be derived from how analysis how memo array is filled!

Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int knapSack(int capacity, vector<int>& weight, vector<int>& profit) {
    int n = weight.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= capacity; ++w) {
            if (weight[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], profit[i - 1] + dp[i - 1][w - weight[i - 1]]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
}

int main() {
    vector<int> profit = { 60, 100, 120 };
    vector<int> weight = { 10, 20, 30 };
    int W = 30;

    int ans = knapSack(W, weight, profit);
    cout << "result " << ans << endl;

    return 0;
}

Iterative solution with 1D array

We can see in earlier solution that the 2D array wastes a lot of cells.

There are a lots of zeros.
Only the last row gives answer.
For calculating the current row of the dp[] array we require only previous row, but if we start traversing the rows from right to left then it can be done with a single row only

So let look at the last row and make logic to use only 1D array.

For sample input weight = [10,20,30] and values = [60,100,120], and capacity=30 the Knapsack 1D dp array is updated as follow.

When no item is yet picked, we initialize dp array to size 31 and fill zero in all cells.
- each cell represents accumulated profit when certain accumulated weight is picked up.

When only itemIndex=0 is picked.
- from accumulated capacity 0 to 30, the profit is all 60.

When itemIndex=1 is processed:
- when accumulated capacity is more than 20 (this item weight), we consider picked or not picked the item.
- dp[w] = max (dp[w] , profit[itemIndex] + dp[capacity -weight[itemIndex])
  - picked the item: profit[itemIndex] + dp[capacity -weight[itemIndex]
  - not picked the item: dp[w] (the profit stored earlier, when only first item is processed.
- we have to use 2 counters, i=itemIndex+1 iterate from 0 to n, and weight from 0 to capacity to iterate

When itemIndex=2 is processed:
- when accumulated capacity is more than 30(this item weight), we consider picked or not picked the item like before.
- the last cell gives the final results.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int knapSack(int capacity, vector<int>& weight, vector<int>& profit) {
    int n = weight.size();
    vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < n; ++i) {
        for (int w = capacity; w >= weight[i]; --w) {
            dp[w] = max(dp[w], profit[i] + dp[w - weight[i]]);
        }
    }
    return dp[capacity];
}

int main() {
    vector<int> profit = { 60, 100, 120 };
    vector<int> weight = { 10, 20, 30 };
    int W = 30;

    int ans = knapSack(W, weight, profit);
    cout << "result " << ans << endl;

    return 0;
}

Problem House Robber

Let attempt this basic "Knapsack" problem, in leetcode, it is called House Robber.

Recursive Solution:

For recursive solution, we construct a decision tree:

every level is day.
on every level, there are choice, rob or no rob.
each node represents to profit earned on a the day. Each node has 2 child nodes, rob or noRob,
- rob is calculated as: nums[day] + calculateProfit(nums, day+2, memo); Notice that we have to skip a day, thus, day+2.
- noRob is calculated as: calculateProfit(nums, day+1, memo)

class Solution {
    int calculateProfit(vector<int>& nums, int day, vector<int>& memo){
        // base case:
        if (day >= nums.size())
            return 0;
        // memo
        if (memo[day] !=-1)
            return memo[day];
        // recurrence case:
        int profit =0;                                                        // profit earned at each node/day
        int profitIfRob = nums[day] + calculateProfit(nums, day+2, memo);     // skip a day
        int profitIfNoRob = calculateProfit(nums, day+1, memo);
        profit += max(profitIfRob, profitIfNoRob);
        memo[day] = max(profitIfRob, profitIfNoRob);
        return memo[day];
    }
public:
    int rob(vector<int>& nums) {
        vector<int> memo(nums.size(),-1);
        return calculateProfit(nums, 0,memo);
    }
};

Iteration solution with 2D arrays.

For a input nums=[2, 7, 9, 3], I could make 2D arrays as follows:

Green cells represents they rob day, and their values are the profit earned upto that day.
The sum on final column represents the sum of the all possible scenarios.
To optimize finding answer while populating the matrix, we could update the best result per row. and update the final answer based on the best of all rows.
Notice the 2 edge cases that could return answer right away. Otherwise, the for loop won't handle the cases.

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() ==1 )
            return nums[0];
        if (nums.size() ==2 )
            return max(nums[0], nums[1]);
        vector<vector<int>> matrix(nums.size(), vector<int> (nums.size(), 0));
        int ans = 0;
        for ( int row = 0; row < nums.size(); row++){    
            matrix[row][row] = nums[row];
            int bestForRow = matrix[row][row];
            for (int col =2; col < nums.size(); col++){
                
                if (matrix[row][col-1] != 0)
                    matrix[row][col] = 0;
                else 
                    matrix[row][col] = matrix[row][col-2] + nums[col];
                bestForRow = max (bestForRow, matrix[row][col]);
            }
            ans = max(ans, bestForRow);
        }

        return ans ;
    }
};

Notes: The above iterative solution with 2D only passes 40/60 test cases on leetcode. For test case like nums=[2,1,1,2], the solution fails! Obviously, the logic doesn't account for scenarios where 2 or more consecutive days are skipped! The 2D array here doesn't really represents the memo matrix in recursive solution which is 1D. Nevertheless, I keep this solution here as a learning lesson.

Iteration solution with 1D arrays

This problem is very similar to the basic Fibbonnaci problem

A few things to remember:

handle edge cases and base cases first.
the program follows iteration through a dp array whose size is usually same as the input array size.
try to understand what each cell in the dp array represents and what they depends on.
- for this problem, each cell represents the profit earned on each day, same as each node in the decision tree mentioned in the recursive solution section.
- each cell depends on 2 possible earlier outcomes (like how parent nodes depends on child nodes). The earlier outcomes are definitely values in previous dp cells.

From the recursive solution, for an input=[2,7,9,3,1] the memo is updated as following:

the memo is filled from rightmost cell first, or memo[input.size()-1].
the final result is returned at leftmost cell or root node, memo[0]

For iterative solution, we should only use the DP array that matches the memo array in recursive solution; however, the direction where cells are updated could be different or even opposite.

the memo is filled from rightmost cell first, root or memo[0].
the final result is returned at leftmost cell or left node, memo[input.size()-1]
cells are updated as traversing leftward. At each cell, 2 choices:
- rob on that day: nums[day] + dp[day-2]
- don't rob on that day. profit is the same at previous day. dp[day-1]

For an input = [10,7,9,100,20] , the DP array is updated as follow:

Note that for above input, we have input[3]=100 being the day with high value, and 2 days before should be skipped! The iteration calculation still accounts for that scenario.
Base cases: 2 first cells are updated first!
Other cases: max(dp[day-1], nums[day] + dp[day-2]);
- note that dp[day-2] stores the best values of the previous days, not just 2 days before! If it is just 2 days before, then it should be nums[day-2], not dp[day-2]!

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];

        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int day = 2; day < nums.size(); day++) {
            dp[day] = max(dp[day-1], nums[day] + dp[day-2]);
        }
        return dp[nums.size()-1];
    }
};

Last thought: The above solution use O(n) space complexity which could be optimized. With some smart implementation, we could solve the above problem without any dp array at all! But that is for another time.