LeetCode - The DP Part

(reference)[https://oi-wiki.org/dp/]

The main idea of DP is to find a way so that if we can solve the i-1th problem, we can solve the ith problem using previous result.

• when we want to find palindromic substrings, we can use a 2d dp to find all the substrings of a string.

        char[] chars = s.toCharArray();
        int len = s.length();
        
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++){
            for (int j = 0; j <= i; j++){
                if (chars[i] == chars[j] && (i - j < 2 || dp[i-1][j+1])){
                    dp[i][j] = true;
                }
            }
        }

and if we want to cut the string into substring with some properties, we can use 1d DP to do this.

• some DP problems needs to pre-fill some values.

buy and sell stock, the initial value of buy should be Integer.MIN_VALUE

linear dp

• single string

LIS: 
    O(n^2) check every one before i

    O(nlogn) use binary search to insert ceiling position (greedy)

• double strings, when we want to compare in two strings, we can use 2d-DP.

LCS:

    dp[i][j] = max(dp[i-1][j], dp[i][j-1])      char at i != char at j

               dp[i-1][j-1] + 1                 char at i == char at j

Interleaving String

• Edit Distance like DP

two directions dp:

use a left dp array to store some info, and a right array.

The final result is made of left and right.