> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/my-algorithm-summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/my-algorithm-summary/chapter1/dynamic-programming.md).

# Dynamic Programming

## Dynamic Programming

## 1. LIS

### (1) Algorithm

```java
    // 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

```java
    // 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](https://leetcode.com/problems/longest-increasing-subsequence/?tab=Description\),%20\[Russian%20Doll%20Envelopes]\(https://leetcode.com/problems/russian-doll-envelopes/?tab=Description\),%20\[Increasing%20Triplet%20Subsequence]\(https://leetcode.com/problems/increasing-triplet-subsequence/?tab=Description)

## 2. Longest Common Subsequence/ Longest Common Substring

### (1) Algorithm

```java
    // 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](https://leetcode.com/problems/edit-distance/?tab=Description\),%20\[Is%20Subsequence]\(https://leetcode.com/problems/is-subsequence/?tab=Description\),%20\[Longest%20Palindromic%20Subsequence]\(https://leetcode.com/problems/longest-palindromic-subsequence/?tab=Description\),%20\[Distinct%20Subsequences]\(https://leetcode.com/problems/distinct-subsequences/?tab=Description\),%20\[Palindrome%20Partitioning%20II]\(https://leetcode.com/problems/palindrome-partitioning-ii/?tab=Description\),%20\[Distinct%20Subsequences]\(https://leetcode.com/problems/distinct-subsequences/?tab=Description), \[Palindrome Partitioning II]\(<https://leetcode.com/problems/palindrome-partitioning-ii/?tab=Description\\>)

## 3. Backpack Problem