Dynamic Programming

DP and Backtracking

Many DP problems can be also solved by backtracking algorithm.

LC 416

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

• Solution using backtracking (recursion):

class Solution {
    public boolean canPartition(int[] nums) {
        boolean result = backtrack(nums, 0, 0, 0);
        return result;
    }

    private boolean backtrack(int[] nums, int index, int left, int right) {
        if (index == nums.length && left == right) {
            return true;
        } else if (index == nums.length) {
            return false;
        }
        boolean includeLeft = backtrack(nums, index+1, left+nums[index], right);
        boolean includeRight = backtrack(nums, index+1, left, right+nums[index]);
        return includeLeft || includeRight;
    }
}

• Idea: Our goal is to partition the array into two subsets, naming them “left” and “right” respectively. For each number in the array, it is either in the “left” subset or “right” subset. We explore all possibilities using recursion.

• Complexity: O(2^n). Thinking about a tree, each node is a backtrack function. The tree is of depth n, each node takes O(1) time.

• Solution using dynamic programming:

Transform the solution to knapsack problem: achieve sum/2 using elements in an array.

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        if (nums[0] < target) {
            dp[nums[0]] = true;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = dp[j] || dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}

• dp[i][j] is boolean, representing whether summation j can be achieved using indexes 0, 1, …, i.
• If nums[i] is used to achieve the summation j, then dp[i-1][j-nums[i]] must be true. If nums[i] is not used to achieve the summation, then dp[i-1][j] must be true.
• Complexity: O(nW), where n is array size, W is array summation.

Optimize Space Complexity

Knapsack Problem

Given bag space N, what is the most valuable way to put items in the bag? One Item can be used only once.

// 2D array
// DP[i][j]: most valuable combination of items for space j using items 0-i.
public static int solve(int M, int N, int[] spaces, int[] values) {
    int[][] dp = new int[M+1][N+1];

    for (int j = spaces[0]; j <= N; j++) {
        dp[0][j] = values[0];
    }

    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            if (j >= spaces[i-1]) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-spaces[i-1]] + values[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[M][N];
}

Use 1D array to solve this:

public static int solve(int M, int N, int[] spaces, int[] values) {
    int[] dp = new int[N+1];
        
    for (int i = spaces[0]; i < N+1; i++) {
        dp[i] = values[0];
    }
    
    for (int i = 1; i < M; i++) {
        for (int j = N; j >= 1; j--) { // iterate from N to 1!
            if (j >= spaces[i]) {
                int takei = dp[j-spaces[i]] + values[i];
                int dtakei = dp[j];
                dp[j] = Math.max(takei, dtakei);
            } else {
                dp[j] = dp[j];
            }
        }
    }
    return dp[N];
}

• In 2D case, each row depends on the values from previous row.
• dp[i][j] depends on dp[i-1][j] and dp[i-1][j-spaces[i-1]], i.e., one top value, one top-left value.
• As a result, in 1D case, update the dp array from right to left.

When to update from left to right? (LC 518)

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

class Solution {
    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length][amount+1];

        for(int i = 0; i < coins.length; i++){
            dp[i][0] = 1;
        }

        for(int j = coins[0]; j <= amount; j++){
            dp[0][j] += dp[0][j-coins[0]];
        }
        
        for(int i = 1; i < coins.length; i++){
            for(int j = 1; j <= amount; j++){
                if(j < coins[i]) dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j];
            }
        }
        return dp[coins.length-1][amount];
    }
}

• Updation: dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j], which depends on both previous row and current row but previous column.

// solution using 1D array
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        for (int i = 0; i < amount+1; i++) {
            if (i % coins[0] == 0) dp[i] = 1;
        }

        for (int i = 1; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}

• At iteration i, dp[j] is the number of combinations that make up amount j, using coins with indexes 0-i.
• Because solution using 2D array uses dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j], so in 1D array, we update from left to right so that dp[j] uses the dp[j-coins[i]] from the same row.