Dynamic Programming

Dynamic Programming

1. LIS

(1) Algorithm

    // Time: O(n^2), Space: O(n)
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // LIS[i] indicate the longest increasing subsequence found at index i
        int[] LIS = new int[nums.length];
        Arrays.fill(LIS, 1);

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && (LIS[j] + 1) > LIS[i]) {
                    LIS[i] = LIS[j] + 1;
                }
            }
        }

        int max = 0;
        for (int i = 0; i < LIS.length; i++) {
            max = Math.max(LIS[i], max);
        }
        return max
    }

(2) Optimization: DP + Binary Search

    // Time: O(nlogn), Space: O(n)
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[] lis = new int[n];
        Arrays.fill(lis, 1);

        int start = 0, end = 0, mid;
        int index = 0;

        for (int num : nums) {
            start = 0;
            end = index;

            while (start < end) {
                mid = start + (end - start) / 2;

                if (lis[mid] < num) {
                    start = mid + 1;
                }
                else {
                    end = mid;
                }
            }
            lis[start] = num;
            if (start == index) index++;
        }
        return index;
    }

(3) Questions

Longest Increasing Subsequence

2. Longest Common Subsequence/ Longest Common Substring

(1) Algorithm

    // Longest Common Subsequence
    public static int LCS(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];

        // The first row and first column is empty string, so dp[i][j] = 0 when i = 0 or j = 0
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }

    // Longest Common Substring
    public static int longestCommonSubstring(String s1, String s2) {
    // Method 2: Dynamic Programming
    int m = s1.length(), n = s2.length();
    int max = 0;
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            max = Math.max(dp[i][j], max);
        }
        else {
            dp[i][j] = 0;
        }
        }
    }
    return max;
    }

(2) Questions

Edit Distance, [Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/?tab=Description\)

3. Backpack Problem