class Solution {
    // Edit Distance
    // dp(i, j) : 把 A[0~i] B[0~j] 變成相同的最小 cost
    // 轉移：
    // 1. i, j 保留 dp(i-1, j-1) if A[i] = B[j]
    // 2. 刪除 i : dp(i-1, j) + cost(A[i])
    // 3. 刪除 j : dp(i, j-1) + cost(B[j])

    // 找出最小 cost 也就等於找出保留最多相等
    // 找出最小 cost 也就等於找出保留最多相等
    
    public int minimumDeleteSum(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        int dp[][] = new int [n + 1][m + 1];
        for(int i = 0; i <= n; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE/2);
        }

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

### LeetCode 1062

lcp(i, j) : suffix[i] 和 suffix[j] 的 longest common prefix
lcp(i, j) = lcp(i+1, j+1) + 1 if (s[i] = s[j])
          = 0 else

lcp(i, j) = lcp(i-1, j-1) - 1



suf[0] : aab]caabdaab
suf[4] : aab]daab
suf[1] :  ab]caabdaab
suf[5] :  ab]daab


每個 substring 都是某個 suffix 的 prefix

### 887. Super Egg Drop

class Solution {
    // 狀態數量： O(k * n), k = 100, n = 10000
    // 轉移時間： O(n) -> O(log n)
    // time : O(k * n log n)
    public int superEggDrop(int k, int n) {
        if (k == 1) return n;

        int ans = n;
        // binary search 
        // while (...)
            int lower = superEggDrop(k - 1, h - 1); // 往下需要的次數
            int higher = superEggDrop(k, n - h); // 往上需要的次數
            int v = max(lower, higher);
            ans = min(ans, v + 1);
        return ans;
    }

    // time : O(k * n^2)
    /* slow
    public int superEggDrop(int k, int n) {
        if (k == 1) return n;

        int ans = n;
        for (int h = 1; h <= n; h++) {
            int lower = superEggDrop(k - 1, h - 1); // 往下需要的次數
            int higher = superEggDrop(k, n - h); // 往上需要的次數
            int v = max(lower, higher);
            ans = min(ans, v + 1);
        }
        return ans;
    }
    */
}

/*
k 個蛋, n 層樓, 最少要試幾次？

dp(k, t) : k 個蛋，t 次，最多可以測多少層樓
dp(1, t) = t
dp(k, t) = dp(k-1, t-1) + dp(k, t-1) + 1
- 有破 dp(1, t-1) ans 介於 [0, h-1]
- 沒有破 dp(2, t-1): ans 介於 [h, h+dp(2,t-1)]

dp(1, 1) = 1
dp(1, 2) = 2
dp(1, 3) = 3

dp(1, 1) = dp(1, 1) = 1
dp(2, 2) = dp(2, 1) + dp(1, 1) + 1 = 3
dp(2, 3) = dp(2, 2) + dp(1, 2) + 1 = 3 + 2 + 1 = 6
dp(2, 4) = dp(2, 3) + dp(1, 3) + 1 = 6 + 3 + 1 = 10
dp(2, 5) = dp(2, 4) + dp(1, 4) + 1 = 10 + 4 + 1 = 15
    第一次丟 h = 3

dp(3, 2) = dp(2, 2) = 3
dp(3, 3) = dp(3, 2) + dp(2, 2) + 1 = 7
dp(3, 4) = dp(3, 3) + dp(2, 3) + 1 = 7 + 6 + 1 = 14
*/