Dynamic Programing

https://leetcode.com/discuss/general-discussion/491522/dynamic-programming-questions-thread. https://www.freecodecamp.org/news/follow-these-steps-to-solve-any-dynamic-programming-interview-problem-cc

509. Fibonacci Number

class Solution {
public:
    int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int one = 0, two = 1, curt = 1;
        for (int i = 2; i <= n; ++i) {
            curt = one + two;
            one = two;
            two = curt;
        }
        return curt;
    }
};

70. Climbing Stairs

dp[i] = dp[i - 1] + dp[i - 2]

public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 2] + dp[i - 1];
    }
    return dp[n];
}

int[] dp;
public int climbStairs(int n) {
    dp = new int[n + 1];
    return dfs(n);
}

private int dfs(int n) {
    if (n <= 1) return 1;
    if (dp[n] != 0) return dp[n];
    int res = dfs(n - 2) + dfs(n - 1);
    dp[n] = res;
    return res;
}

377. Combination Sum IV

public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int i = 1; i <= target; i++) {
        for (int j : nums) {
            if (i - j >= 0) {
                dp[i] += dp[i - j];
            }
        }
    }
    return dp[target];
}

62. Unique Paths

initialization: dp[0][0] = 1, dp[i][j] = 1 when i == 0 or j == 0
transition: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[m - 1][n - 1];
}

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < m; i++) {
        int[] newRow = new int[n];
        for (int j = 0; j < n; j++) {
            if (j == 0) {
                newRow[j] = 1;
            } else {
                newRow[j] = dp[j] + newRow[j - 1];
            }
        }
        dp = newRow;
    }
    return dp[n - 1];
}

63. Unique Paths II

When obstacle[i][j] == 1, there is no way to reach to that grid, which means dp[i][j] = 0.

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int[][] dp = new int[m][n];
    if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
    dp[0][0] = 1;
    for (int i = 1; i < m; i++) {
        if (obstacleGrid[i][0] != 1) {
            dp[i][0] = dp[i - 1][0];
        }
    }
    for (int i = 1; i < n; i++) {
        if (obstacleGrid[0][i] != 1) {
            dp[0][i] = dp[0][i - 1];
        }
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[m - 1][n - 1];
}

980. Unique Paths III DFS + Memo

198. House Robber

Transition: dp[i] is the max value of get max from i - 2 plus the current one, and the max of i - 2 (not choose the current one) : dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);

Initialization: dp[0] = nums[0], dp[1] = Math.max(nums[0], nums[1])

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    if (n == 1) return nums[0];
    if (n == 2) return Math.max(nums[0], nums[1]);
    int[] dp = new int[n];
    if (n == 1) return nums[0];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[n - 1];
}

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    if (n == 1) return nums[0];
    int nottakelast = nums[0];
    int takelast = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        int temp = Math.max(nottakelast + nums[i], takelast);
        nottakelast = takelast;
        takelast = temp;
    }
    return Math.max(nottakelast, takelast);
}

213. House Robber II

Do the same calculation as 198 but in two different ranges:

0 to n - 2
1 to n - 1

Get the max of the dp result of both ranges.

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    if (n == 1) return nums[0];
    if (n == 2) return Math.max(nums[0], nums[1]);
    return Math.max(robhelper(nums, 0, n - 2), robhelper(nums, 1, n - 1));
}

private int robhelper(int[] nums, int start, int end) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    int nottakelast = nums[start];
    int takelast = Math.max(nums[start], nums[start + 1]);
    for (int i = start + 2; i <= end; i++) {
        int temp = Math.max(nottakelast + nums[i], takelast);
        nottakelast = takelast;
        takelast = temp;
    }
    return Math.max(nottakelast, takelast);
}

337. House Robber III

DP on Tree. Bottom up traversal. Keep the max result at each node. There are two options to get the best solution at the current node:

take self value: but not take the value from left and right child
not take self value: only take max of left child and max of right child.

public int rob(TreeNode root) {
    int[] res = helper(root);
    return Math.max(res[0], res[1]);
}

private int[] helper(TreeNode curt) {
    if (curt == null) return new int[]{0, 0};
    int[] left = helper(curt.left);
    int[] right = helper(curt.right);
    int takeself = left[1] + right[1] + curt.val;
    int nottakeself = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return new int[]{takeself, nottakeself};
}

221. Maximal Square

The maximal square is determined from its shortest edge at dp[i][j]. For example, the edge of:

111

110

gives dp result:

1 2 3

1 2 0

In this case

public int maximalSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m + 1][n + 1];
    int res = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (matrix[i - 1][j - 1] == '1') {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                res = Math.max(res, dp[i][j]);
            }
        }
    }
    return res * res;
}

public int maximalSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m][n];
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] != '1') {
                continue;
            }
            int top = i > 0 ? dp[i-1][j] + 1: 1;
            int left = j > 0 ? dp[i][j - 1] + 1: 1;
            int lefttop = i > 0 && j > 0 ? dp[i-1][j- 1] + 1 : 1;
            dp[i][j] = Math.min(Math.min(top, left), lefttop);
            res = Math.max(res, dp[i][j]);
        }
    }
    return res * res;
}

120. Triangle

public int minimumTotal(List<List<Integer>> triangle) {
    int len = triangle.size();
    for (int i = 1; i < len; i++) {
        for (int j = 0; j < triangle.get(i).size(); j++) {
            int LEFT  = j > 0  ? triangle.get(i - 1).get(j - 1) : Integer.MAX_VALUE;
            int RIGHT = j < triangle.get(i - 1).size() ? triangle.get(i - 1).get(j) : Integer.MAX_VALUE;
            triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(LEFT, RIGHT));
        }
    }
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < triangle.get(len - 1).size(); i++) min = Math.min(min, triangle.get(len - 1).get(i));
    return min;
}

53. Maximum Subarray

dp[i] : max contiguous subarray sum at i

dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        max = Math.max(max, dp[i]);
    }
    return max;
}

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int curt = nums[0];
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        curt = Math.max(curt + nums[i], nums[i]);
        max = Math.max(max, curt);
    }
    return max;
}

55. Jump Game

dp[i + k] : can jump to i + k position

dp[i + k] = dp[i] + k

public boolean canJump(int[] nums) {
    int n = nums.length;
    boolean[] dp = new boolean[n];
    dp[0] = true;
    for (int i = 0; i < n; i++) {
        if (dp[i]) {
            for (int k = 0; k <= nums[i]; k++) {
                if (i + k == n - 1) return true;
                dp[i + k] = true;
            }
        }
    }
    return dp[n - 1];
}

45. Jump Game II

int jump(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, INT_MAX);
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= nums[i] && j + i < n; ++j) {
            dp[i + j] = min(dp[i + j], dp[i] + 1);
        }
    }
    return dp[n - 1];
}

64. Minimum Path Sum

Either move down or right, which means it comes from left and up. Find the minimum from the left and up, add to the curt grid.

T: O(m * n) S: O(1)

    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }

256. Paint House

Get min on each grid.

public int minCost(int[][] costs) {
    if (costs == null || costs.length == 0 || costs[0].length == 0) {
        return 0;
    }
    int n = costs.length;
    for (int i = 1; i < n; i++) {
        costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
        costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
        costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
    }
    int min = Integer.MAX_VALUE;
    for (int k = 0; k < 3; k++) {
        min = Math.min(min, costs[n - 1][k]);
    }
    return min;
}

265. Paint House II

Use two pointers to store the min and second min on the node.

public int minCostII(int[][] costs) {
    if (costs == null || costs.length == 0) return 0;
    int colors = costs[0].length;
    int min1 = -1;
    int min2 = -1;
    for (int i = 0; i < costs.length; i++) {
        int last1 = min1;
        int last2 = min2;
        min1 = -1;
        min2 = -1;
        for (int k = 0; k < colors; k++) {
            if (k != last1) {
                costs[i][k] += last1 == -1 ? 0 : costs[i - 1][last1];
            } else {
                costs[i][k] += last2 == -1 ? 0 : costs[i - 1][last2];
            }
            
            if (min1 == -1 || costs[i][k] < costs[i][min1]) {
                min2 = min1;
                min1 = k;
            } else if (min2 == -1 || costs[i][k] < costs[i][min2]) {
                min2 = k;
            }
        }
    }
    return costs[costs.length - 1][min1];
}

322. Coin Change

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int c : coins) {
            if (i - c >= 0 && dp[i - c] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i - c] + 1, dp[i]);
            }
        } 
    }
    return dp[amount] == Integer.MAX_VALUE ?  -1 : dp[amount];
}

746. Min Cost Climbing Stairs

dp[i] = Math.min(dp[i - 1] + cost[i], dp[i - 2] + cost[i])

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n];
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < n; i++) {
       dp[i] = Math.min(dp[i - 1] + cost[i], 
                        dp[i - 2] + cost[i]);
    }
    return Math.min(dp[n - 1], dp[n - 2]);
}

1155. Number of Dice Rolls With Target Sum

dp[i][j] : the number of possible ways to roll j dices so the sum of the face up numbers equals i

dp[i][j] += dp[i - face][j - 1] where 1 <= face <= f and i - d >= 0

initialization: dp[0][0] = 1

int MOD = 1000000007;
public int numRollsToTarget(int d, int f, int target) {
    int[][] dp = new int[d + 1][target + 1];
    dp[0][0] = 1;
    for (int i = 1; i <= d; i++) {
        for (int j = 1; j <= target; j++) {
            if (j > i * f) continue;
            for (int k = 1; k <= f; k++) {
                if (j < k) break;
                dp[i][j] += dp[i - 1][j - k];
                dp[i][j] = dp[i][j] % MOD;
            }
        }
    }
    return dp[d][target];
}

494. Target Sum

dp[i][j]: how many ways to assign symbols to make sum of j nums equal to target i.

dp[i][j] = dp[i - nums[j]][j - 1] + dp[i + nums[j]][j - 1]

Since it includes the negative number and the total sum will not exceed 1000. Therefore the answer range is between -1000 and 1000. Shift everything to make it fit the matrix, which is 0 to 2001.

dp[i][sum - nums[i] + 1000] += dp[i - 1][sum + 1000]
dp[i][sum + nums[i] + 1000] += dp[i - 1][sum + 1000]

public int findTargetSumWays(int[] nums, int S) {
    int n = nums.length;
    int[][] dp = new int[n][2001];
    dp[0][nums[0] + 1000] = 1;
    dp[0][-nums[0] + 1000] += 1;
    for (int i = 1; i < n; i++) {
        for (int sum = -1000; sum <= 1000; sum++) {
            if (dp[i - 1][sum + 1000] > 0) {
                dp[i][sum - nums[i] + 1000] += dp[i - 1][sum + 1000];
                dp[i][sum + nums[i] + 1000] += dp[i - 1][sum + 1000];
            }
        }
    }
    return S <= 1000 ? dp[n - 1][S + 1000] : 0;
}

416. Partition Equal Subset Sum

Check if the sum of all elements can be divided by 2, and array of numbers can sum up to sum / 2.

dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]] if j - nums[i - 1] >= 0

public boolean canPartition(int[] nums) {
    if (nums == null || nums.length == 0) return true;
    int n = nums.length;
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) return false;
    sum /= 2;
    boolean[][] dp = new boolean[n + 1][sum + 1];
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= sum; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j - nums[i - 1] >= 0) {
                dp[i][j] |= dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    return dp[n][sum];
}

300. Longest Increasing Subsequence

Dp:

dp[i] represents the LIS up to index i.
Init, fill dp array with 1 since the LIS of a single element is 1.

T: O(n ^ 2) S: O(n)

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 0; i < nums.length; i++) {
            int max = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    max = Math.max(max, dp[j]);
                }
            }
            dp[i] = max + 1;
            res = Math.max(max, res);
        }
        return res;
    }

DP: Binary Search T: O(nlogn) link

1027. Longest Arithmetic Subsequence

Solution1: for each number in the array, save it is difference and the longest arithmetic subsequence of that difference. T: O(n^2)

public int longestArithSeqLength(int[] A) {
    if (A.length <= 1) return A.length;
    int n = A.length;
    Map<Integer, Integer>[] dp = new HashMap[n];
    for (int i = 0; i < A.length; i++) {
        dp[i] = new HashMap<Integer, Integer>();
    }
    int res = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int diff = A[i] - A[j];
            int len = 2;
            if (dp[j].containsKey(diff)) {
                len = dp[j].get(diff) + 1;
            }
            dp[i].put(diff, len);
            res = Math.max(res, len);
        }
    }
    return res;
}

Use relation: A[k] = 2 * A[j] - A[i] where i < j < k to find the k and save the index of k to an array: T: O(n^2)

public int longestArithSeqLength(int[] A) {
    int n = A.length;
    int[][] dp = new int[n][n];
    int[] indices = new int[1001];
    Arrays.fill(indices, -1);
    int max = 2;
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i], 2);
        for (int j = i + 1; j < n; j++) {
            int num = A[i] * 2 - A[j];
            if (num >= 0 && indices[num] != -1) {
                dp[i][j] = dp[indices[num]][i] + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
        indices[A[i]] = i;
    }
    return max;
}

1218. Longest Arithmetic Subsequence of Given Difference

Similar as two sum technique, search for arr[i] - diff in the hashmap and extend its length if there is a value.

public int longestSubsequence(int[] arr, int difference) {
    Map<Integer, Integer> count = new HashMap<>();
    int res = 1;
    for (int i = 0; i < arr.length; i++) {
        if (count.containsKey(arr[i] - difference)) {
            count.put(arr[i], count.get(arr[i] - difference) + 1);
        } else {
            count.put(arr[i], 1);
        }
        res = Math.max(res, count.get(arr[i]));
    }
    return res;
}

688. Knight Probability in Chessboard

Use DP to calculate the probability to reach each grid on the next level. Then sums up the probabilities on all grids.

    int[][] dirs = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2,1}, {-2,1}, {2,-1}, {-2,-1}};
    public double knightProbability(int N, int K, int r, int c) {
        double[][] dp = new double[N][N];
        dp[r][c] = 1;
        while (K-- > 0) {
            double[][] dp2 = new double[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int[] dir : dirs) {
                        int next_x = i + dir[0];
                        int next_y = j + dir[1];
                        if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < N) {
                            dp2[next_x][next_y] += dp[i][j] / 8.0;
                        }
                    }
                }
            }
            dp = dp2;
        }
        double res = 0.0;
        for (double[] row : dp) {
            for (double d : row) {
                res += d;
            }
        }
        return res;
    }

935. Knight Dialer

Starts with all 10 numbers as 1, rolling save all combinations from the past and mod by modulo.

int[][] moves = new int[][]{ {4, 6}, {8, 6}, {7, 9}, {4, 8},
                            {3, 9, 0}, {}, {1, 7, 0},
                            {2, 6}, {1, 3}, {2, 4}};
public int knightDialer(int n) {
    int MOD = 1000000007;
    int[] dp = new int[10];
    Arrays.fill(dp, 1);
    while (--n > 0) {
        int[] temp = new int[10];
        for (int k = 0; k <= 9; k++) {
            for (int next : moves[k]) {
                temp[next] += dp[k];
                temp[next] %= MOD;
            }
        }
        dp = temp;
    }
    int res = 0;
    for (int i = 0; i < 10; i++) {
        res += dp[i];
        res %= MOD;
    }
    return res;
}

96. Unique Binary Search Trees

public int numTrees(int n) {
    int[] G = new int[n + 1];
    G[0] = 1;
    G[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            G[i] += G[j - 1] * G[i - j];
        }
    }
    return G[n];
}

650. 2 Keys Keyboard

dp[i] = min = Math.min(dp[j] + (i / j), dp[i / j] + j)

public int minSteps(int n) {
    int[] dp = new int[n + 1];
    for (int i = 2; i <= n; i++) {
        int min = i;
        for (int j = 2; j < i; j++) {
            if (i % j == 0) { 
                min = Math.min(min, 
                    Math.min(dp[j] + (i / j), 
                    dp[i / j] + j));
            }
        }
        dp[i] = min;
    }
    return dp[n];
}

Initialize a map to store the current stone and the steps it can reach. Loop over the stones and create empty HashSets for all stones. Put <0, [1]> in the map to make sure that the frog move the first step.

Loop over the stones except the last one (i < stones.length - 1), get the next steps of the current stone, if stone + step reach the last stone (stone + step == stones[stones.length - 1]), return true.

Otherwise, add the k + 1, k , k - 1 step to map.get(stone + step), it indicates how many steps frog can move on the next stone.

    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        map.put(0, new HashSet<>());
        map.get(0).add(1);
        for (int i = 1; i < stones.length; i++) {
            map.put(stones[i], new HashSet<>());
        }
        for (int i = 0; i < stones.length - 1; i++) {
            int stone = stones[i];
            for (int step : map.get(stone)) {
                if (stone + step == stones[stones.length - 1]) {
                    return true;
                }
                Set<Integer> nextset = map.get(stone + step);
                if (nextset != null) {
                    nextset.add(step);
                    if (step - 1 > 0) nextset.add(step - 1);
                    nextset.add(step + 1);
                }
            }
        }
        return false;
    }

312. Burst Balloons

    public int maxCoins(int[] iNums) {
        int[] nums = new int[iNums.length + 2];
        int n = 1;
        for (int x : iNums) {
            nums[n++] = x;
        }
        nums[0] = nums[n++] = 1;
        
        int[][] dp = new int[n][n];
        for (int k = 2; k < n; k++) {
            for (int left = 0; left < n - k; left++) {
                int right = left + k;
                for (int i = left + 1; i < right; i++) {
                    dp[left][right] 
                        = Math.max(dp[left][right],
                                  nums[left] * nums[i] * nums[right]
                                  + dp[left][i] + dp[i][right]);
                }
            }
        }
        return dp[0][n - 1];
    }

97. Interleaving String

public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length(), len2 = s2.length();
        if(s3.length() != len1 + len2){
            return false;
        }
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;
        for(int i = 1; i <= len1; i++){ //base case, go down
            dp[i][0] = dp[i - 1][0] && (s1.charAt(i - 1) == s3.charAt(i - 1));
        }
        for(int i = 1; i <= len2; i++){  //base case, go right
            dp[0][i] = dp[0][i - 1] && (s2.charAt(i - 1) == s3.charAt(i - 1));
        }
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                //case 1, special case, up and left has the same character.
                if(s1.charAt(i - 1) == s3.charAt(i + j - 1) && s2.charAt(j - 1) == s3.charAt(i + j - 1)){
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                //case2, normal case, only from left
                }else if(s1.charAt(i - 1) == s3.charAt(i + j - 1)){
                    dp[i][j] = dp[i - 1][j];
                //case3, normal case, only from up
                }else if(s2.charAt(j - 1) == s3.charAt(i + j - 1)){
                    dp[i][j] = dp[i][j - 1];
                }
                /*pay attention, no other cases here,think of: s1 = abc, s2 = def, s3 = abcdef,
                while dp[2][1] will be one of "abd,adb, bad, bda, dab, dba", and we try to match "abc" no match!
                Think of this problem as a matrix, we are tring to find out if there is a path from [0,0]  to [len1 - 1, len2 - 1], 
                so dp[i][j] == false, only mean dp[i][j] is not on the valid path, does not mean there is no such path exists!
                   a  b  c
                   ☑️ ☑️ ☑️
            d               ☑️
            e               ☑️
            f               ☑️(valid path)
            */
            }
        }
        return dp[len1][len2];
    }

10. Regular Expression Matching

public boolean isMatch(String s, String p) {
    if (s == null || p == null) {
        return false;
    }
    int m = s.length(), n = p.length();
    return helper(s, 0, p, 0, new boolean[m][n], new boolean[m][n]);
}

private boolean helper(String s, int i, String p, int j, boolean[][] visited, boolean[][] memo) {
    if (j == p.length()) return i == s.length();
    if (i == s.length()) return matchpattern(p, j);
    if (visited[i][j]) return memo[i][j];
    boolean match = false;
    if (j + 1 < p.length() && p.charAt(j + 1) == '*') { 
        match = ((s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') && helper(s, i + 1, p, j, visited, memo))
            || helper(s, i, p, j + 2, visited, memo);
    } else if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
        match = helper(s, i + 1, p, j + 1, visited, memo);
    }  
    visited[i][j] = true;
    memo[i][j] = match;
    return match;
}

private boolean matchpattern(String p, int start) {
    for (int i = start; i < p.length(); i += 2) {
        if (i + 1 >= p.length() || p.charAt(i + 1) != '*') return false;
    }
    return true;
}

public boolean isMatch(String s, String p) {
    if (s == null || p == null) return false;
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    dp[0][0] = true;
    
    for (int i = 0; i < p.length(); i++) {
        if (p.charAt(i) == '*' && dp[0][i-1]) {
            dp[0][i+1] = true;
        }
    }
    
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < p.length(); j++) {
     if (p.charAt(j) == '.') {
            dp[i+1][j+1] = dp[i][j];
        }
        if (p.charAt(j) == s.charAt(i)) {
            dp[i+1][j+1] = dp[i][j];
        }
        if (p.charAt(j) == '*') {
            if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                dp[i+1][j+1] = dp[i+1][j-1];
            } else {
                dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
            }
        }
        }
    }
    return dp[s.length()][p.length()];
}

44. Wildcard Matching

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] visited = new boolean[m][n];
    boolean[][] memo = new boolean[m][n];
    return helper(s, 0, p, 0, visited, memo);
}

private boolean helper(String s, int i, String p, int j, boolean[][] visited, boolean[][] memo) {
    if (j == p.length()) {
        return i == s.length();
    }
    if (i == s.length()) {
        return allStar(p, j);
    }
    if (visited[i][j]) {
        return memo[i][j];
    }
    boolean match = false;
    if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
        match = helper(s, i + 1, p, j + 1, visited, memo);
    } else if (p.charAt(j) == '*') { // "*" scenario
        match = helper(s, i, p, j + 1, visited, memo) || helper(s, i + 1, p, j, visited, memo);
    }
    visited[i][j] = true;
    memo[i][j] = match;
    return match;
}

private boolean allStar(String p, int pIndex) {
    for (int i = pIndex; i < p.length(); i++) {
        if (p.charAt(i) != '*') {
            return false;
        }
    }
    return true;
}

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        if (p.charAt(i - 1) == '*') {
            dp[0][i] = true;
        } else break;
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][ j - 1];
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?');
            }
        }
    }
    return dp[m][n];
}

Card Game

Two players take turns to take cards in a row. Each player take from 1 to 3 cards. Compute the max of the first player gets.

1140. Stone Game II

public int stoneGameII(int[] piles) {
    int[] presum = Arrays.copyOf(piles, piles.length);
    int n = piles.length;
    for (int i = presum.length - 2; i >= 0; i--) {
        presum[i] += presum[i + 1];
    }
    return helper(presum, 0, 1, new int[n][n]);
}

private int helper(int[] presum, int startIndex, int M, int[][] memo) {
    if (startIndex + 2 * M >= presum.length) {
        return presum[startIndex];
    }
    if (memo[startIndex][M] > 0) return memo[startIndex][M];
    int take = 0, res = 0;
    for (int k = 1; k <= M * 2; k++) {
        take = presum[startIndex] - presum[startIndex + k];
        res = Math.max(res, take + presum[startIndex + k] - helper(presum, startIndex + k, Math.max(M, k), memo));
    }
    memo[startIndex][M] = res;
    return res;
}

562. Longest Line of Consecutive One in Matrix

3D dp. There are four scenarios: hori, verti, diag, adiag. For each scenario we need to maintain a 2D dp matrix so that it is a 3D dp.

public int longestLine(int[][] M) {
    if (M == null || M.length == 0 || M[0].length == 0) return 0;
    int m = M.length, n = M[0].length;
    int[][][] dp = new int[m][n][4];
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (M[i][j] == 1) {
                for (int k = 0; k < 4; k++) {
                    dp[i][j][k] = 1;
                }
                if (i > 0 && dp[i - 1][j][0] != 0) {
                    dp[i][j][0] += dp[i - 1][j][0];
                }
                if (j > 0 && dp[i][j - 1][1] != 0) {
                    dp[i][j][1] += dp[i][j - 1][1];
                }
                if (i > 0 && j > 0 && dp[i - 1][j - 1][2] != 0) {
                    dp[i][j][2] += dp[i - 1][j - 1][2];
                }
                if (i > 0 && j < n - 1 && dp[i - 1][j + 1][3] != 0) {
                    dp[i][j][3] += dp[i - 1][j + 1][3];
                }
                for (int k = 0; k < 4; k++) {
                    res = Math.max(res, dp[i][j][k]);
                }
            }
        }
    }
    return res;
}

975. Odd Even Jump

This is a tricky question. It asks if jump odd step, with the smallest number above current. If jump even step, with the largest number above current. This can be achieve by using TreeMap. Here are the rules:

During odd numbered jumps (ie. jumps 1, 3, 5, ...), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
During even numbered jumps (ie. jumps 2, 4, 6, ...), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.

Loop over the array from end. This is due to we can reversely determine the start step from the end step. Initialize two boolean arrays to determine if it can reach by odd jumps or even jumps. Put the number and its index to the TreeMap.

public int oddEvenJumps(int[] A) {
    int n = A.length;
    boolean[] hi = new boolean[n]; //  
    boolean[] lo = new boolean[n]; //
    hi[n - 1] = true;
    lo[n - 1] = true;
    TreeMap<Integer, Integer> map = new TreeMap<>();
    map.put(A[n - 1], n - 1);
    int count = 1;
    for (int i = n - 2; i >= 0; i--) {
        Integer floor = map.floorKey(A[i]);
        Integer ceiling = map.ceilingKey(A[i]);
        if (floor != null) { // even
            hi[i] = lo[map.get(floor)];
        } 
        if (ceiling != null) { // odd
            lo[i] = hi[map.get(ceiling)];
        }
        map.put(A[i], i);
        if (lo[i]) count++;
    }
    return count;
}

741. Cherry Pickup

Walk twice from (0,0) to (m - 1, n - 1) which gives the same result from walk over and walk back. DFS will TLE

public int cherryPickup(int[][] grid) {
    if(grid == null || grid.length == 0 || grid[0].length == 0)
        return 0;

    int res = helper(grid, 0, 0, true);
    return Math.max(res, 0);
}

private int helper(int[][] grid, int x, int y, boolean round1) {
    if (x >= grid.length || y >= grid[0].length || grid[x][y] == -1) {
        return Integer.MIN_VALUE;
    }
    int temp = grid[x][y];
    grid[x][y] = 0;
    int res;
    if (x == grid.length - 1 && y == grid[0].length - 1) {
        res = round1 ? helper(grid, 0, 0, false) : 0;
    } else {
        int right = helper(grid, x, y + 1, round1);
        int down = helper(grid, x + 1, y, round1);
        res = Math.max(right, down);
        
    }
    grid[x][y] = temp;
    return res + temp;
}

DP explanation

public int cherryPickup(int[][] grid) {
    int N = grid.length, M = (N << 1) - 1;
    int[][] dp = new int[N][N];
    dp[0][0] = grid[0][0];

    for (int n = 1; n < M; n++) {
        for (int i = N - 1; i >= 0; i--) {
            for (int p = N - 1; p >= 0; p--) {
                int j = n - i, q = n - p;

                if (j < 0 || j >= N || q < 0 || q >= N || grid[i][j] < 0 || grid[p][q] < 0) {
                    dp[i][p] = -1;
                    continue;
                 }

                 if (i > 0) dp[i][p] = Math.max(dp[i][p], dp[i - 1][p]);
                 if (p > 0) dp[i][p] = Math.max(dp[i][p], dp[i][p - 1]);
                 if (i > 0 && p > 0) dp[i][p] = Math.max(dp[i][p], dp[i - 1][p - 1]);

                 if (dp[i][p] >= 0) dp[i][p] += grid[i][j] + (i != p ? grid[p][q] : 0);
             }
         }
    }

    return Math.max(dp[N - 1][N - 1], 0);
}

1463. Cherry Pickup II

Walk two robots simultaneously. First has 3 steps: left down, down, right down. Same thing for the 2nd one.

DFS + MEMO: TLE

public int cherryPickup(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Integer[][][] dp = new Integer[m][n][n];
    return dfs(grid, m, n, 0, 0, n - 1, dp);
}

private int dfs(int[][] grid, int m, int n, int r, int c1, int c2, Integer[][][] dp) {
    if (r == m) return 0;
    if (dp[r][c1][c2] != null) return dp[r][c1][c2];
    int res = 0;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            int nc1 = c1 + i, nc2 = c2 + j;
            if (nc1 >= 0 && nc1 < n && nc2 >= 0 && nc2 < n) {
                res = Math.max(res, dfs(grid, m, n, r + 1, nc1, nc2, dp));
            }
        }
    }
    if (c1 == c2) {
        res +=  grid[r][c1];
    } else {
        res += grid[r][c1] + grid[r][c2];
    }
    return res;
}

public int cherryPickup(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    // dp[r][c1][c2]: starting from row r, column c1 and c2, max # of cherries.
    int[][][] dp = new int[m][n][n];
    for(int r = m - 1; r >= 0; r--) {
        for(int c1 = 0; c1 < n; c1++) {
            for(int c2 = 0; c2 < n; c2++) {
                int val = (c1 == c2) ? grid[r][c1] : grid[r][c1] + grid[r][c2];
                if(r == m - 1) {
                    dp[r][c1][c2] = val;
                    continue;
                }
                int next = 0;
                for(int i = -1; i <= 1; i++) {
                    for(int j = -1; j <= 1; j++) {
                        int c1_n = c1 + i, c2_n = c2 + j;
                        if(c1_n >= 0 && c1_n < n && c2_n >= 0 && c2_n < n) {
                            next = Math.max(next, dp[r + 1][c1_n][c2_n]);
                        }
                    }
                }
                dp[r][c1][c2] = val + next;
            }
        }
    }
    return dp[0][0][n - 1];
}

3466. Maximum Coin Collection

class Solution {
    public long maxCoins(int[] lane1, int[] lane2) {
        int n = lane1.length;
        // dp[pos][lane][switchesLeft]: max coins at position `pos`, in `lane` (0 or 1), with `switchesLeft` switches remaining
        long[][][] dp = new long[n][2][3];

        // Initialization at position 0
        dp[0][0][2] = lane1[0]; // Start on lane 0 with 2 switches remaining
        dp[0][0][0] = lane1[0]; // Special case: no switches allowed at all
        dp[0][1][1] = lane2[0]; // Start on lane 1 with 1 switch remaining

        long maxCoins = Math.max(dp[0][0][2], dp[0][1][1]);

        for (int pos = 1; pos < n; pos++) {
            // lane 0, 0 switches left:
            //   - Stay on lane 0 from previous step with 0 switches
            //   - Or switch from lane 1 using the last switch
            dp[pos][0][0] = Math.max(dp[pos - 1][0][0], dp[pos - 1][1][1]) + lane1[pos];

            // lane 0, 2 switches left:
            //   - Continue on lane 0 without switching
            //   - Or reset here (if this is the first move)
            dp[pos][0][2] = Math.max(dp[pos - 1][0][2] + lane1[pos], lane1[pos]);

            // lane 1, 1 switch left:
            //   - Stay on lane 1 with 1 switch left
            //   - Or switch from lane 0 with 2 switches left
            //   - Or start from here
            dp[pos][1][1] = Math.max(Math.max(dp[pos - 1][1][1], dp[pos - 1][0][2]), 0) + lane2[pos];

            // Track best result so far
            long currentMax = Math.max(Math.max(dp[pos][0][0], dp[pos][0][2]), dp[pos][1][1]);
            maxCoins = Math.max(maxCoins, currentMax);
        }

        return maxCoins;
    }
}

3610. Minimum Number of Primes to Sum to Target

class Solution {
    int min = Integer.MAX_VALUE;
    public int minNumberOfPrimes(int n, int m) {
        List<Integer> primes = getFirstNPrimes(m);
        // DP approach - similar to coin change problem
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            int min = dp[i];
            for (int prime : primes) {
                if (prime > i) break;
                if (dp[i - prime] == Integer.MAX_VALUE) continue;
                min = Math.min(min, dp[i - prime] + 1);
            }
            dp[i] = min;
        }
        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
      /**
     * Returns the first n prime numbers using Sieve of Eratosthenes with upper bound estimation
     * @param n the number of primes to find
     * @return List of the first n prime numbers
     */
    public static List<Integer> getFirstNPrimes(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("n must be positive");
        }
        
        // Handle small cases directly
        List<Integer> primes = new ArrayList<>();
        if (n >= 1) primes.add(2);
        if (n >= 2) primes.add(3);
        if (n >= 3) primes.add(5);
        if (n >= 4) primes.add(7);
        if (n >= 5) primes.add(11);
        if (n >= 6) primes.add(13);
        
        if (n <= 6) {
            return primes.subList(0, n);
        }
        
        // Estimate upper bound using prime number theorem approximation
        int upperBound = estimateUpperBound(n);
        
        // Keep expanding the bound until we find enough primes
        while (true) {
            // Create sieve array
            boolean[] isPrime = new boolean[upperBound + 1];
            Arrays.fill(isPrime, true);
            isPrime[0] = false;
            isPrime[1] = false;
            
            // Sieve of Eratosthenes
            for (int i = 2; i * i <= upperBound; i++) {
                if (isPrime[i]) {
                    for (int j = i * i; j <= upperBound; j += i) {
                        isPrime[j] = false;
                    }
                }
            }
            
            // Collect primes into list
            List<Integer> foundPrimes = new ArrayList<>();
            for (int i = 2; i <= upperBound && foundPrimes.size() < n; i++) {
                if (isPrime[i]) {
                    foundPrimes.add(i);
                }
            }
            
            // Return first n primes if we found enough
            if (foundPrimes.size() >= n) {
                return foundPrimes.subList(0, n);
            }
            
            // If we didn't find enough primes, double the upper bound
            upperBound *= 2;
        }
    }
    
    /**
     * Estimates upper bound for the nth prime using prime number theorem
     * Formula: p_n ≈ n * ln(n) + n * ln(ln(n)) for n >= 6
     */
    private static int estimateUpperBound(int n) {
        if (n < 6) return 15;
        
        double logN = Math.log(n);
        double logLogN = Math.log(logN);
        
        // Using refined approximation with safety factor
        double estimate = n * (logN + logLogN - 1 + (logLogN - 2) / logN);
        
        // Add safety factor to ensure we don't underestimate
        return (int) Math.ceil(estimate * 1.1);
    }
}

PreviousTraveling Salesman Problem (TSP)NextDP on String

Last updated 7 months ago

hashtagCard Game

Card Game