LeetCode Problem: Dynamic Programming Topics

1. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"

Here is the code:

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        if (s.length() == 0 || s.trim().length() == 0) {
            return s;
        }

        int len = s.length();
        boolean[][] dp = new boolean[len][len];

        String ans = "";
        int max = 0;
        for (int i = 0; i < len; i++) {

            for (int j = 0; j <= i; j++) {

                // Fill in the dp table
                boolean judge = s.charAt(i) == s.charAt(j);
                if (j - i > 2) {
                    dp[i][j] = dp[i + 1][j - 1] && judge;
                } else {
                    // Three cases:
                    // 1. j - i == 0, e.g., "a"
                    // 2. j - i == 1, e.g., "ab", "aa"
                    // 3. j - i == 2, e.g., "abc", "aba"
                    dp[i][j] = judge;
                }

                // Find the longest palindromic substring
                if (dp[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    ans = s.substring(i, j + 1);
                }
            }
        }
        return ans;
    }
}

The process of above code is like this:

---

2. Longest Arithmetic Sequence

Given an array A of integers, return the length of the longest arithmetic subsequence in A. For example:

---

3. House Robber

We need to use dynamic programming to solve this problem:

public class HouseRobber {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        
        int[] dp = new int[len + 1];
        dp[0] = 0;
        dp[1] = nums[0];

        for (int i = 1; i < len; i++) {
            // dp[2] = Math.max(dp[1], dp[0] + nums[1])
            dp[i + 1] = Math.max(dp[i], dp[i - 1] + nums[i]);
        }

        return dp[len];
    }
}

The process of the above code is like this:

---

4. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Here is the code to solve the problem:

public class MaximumSubarray {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];

        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 1], nums[i]);
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

The process of the above code is like this:

---

5. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.

Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: -1

Here is the code to solve the problem:

public class CoinChange {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);// amount + 1 is just a placeholder.
        dp[0] = 0;

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

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

The process of the above code is like this:

---

6. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:
Input: amount = 10, coins = [10] 
Output: 1

Here is the code to solve the problem:

public class CoinChange2 {
    public int change(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

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

The process of the above code is like this:

---