DP

有朋友提到不知道怎么做DP的题目，分享一下自己的总结，希望对大家有帮助。


1. Distinct Subsequence  (String S, String T)
     F(i, j) =  F(i-1, j)                  , S[i] != T[j]
                  F(i-1, j) + F(i-1, j-1) , S[i] ==T[j]

2. Longest Common Subsequence (String S1, String S2)
    F(i, j) =  F(i-1, j-1) + 1, S[i] == T[j]
                 Max{ F(i-1, j),  F(i, j-1) }, S[i] !=T[j]

    LCS可以把空间复杂度O(n^2)减少到O(n),因为第n步的DP只 和前一步(第n-1步)的
最优子结果有关 F(n) = F(n-1)

3. Edit Distance  (String S1, String S2)          
     F(i, j) = Min { F(i-1, j) + 1, F(i, j-1) + 1, F(i-1, j-1)  }     , S1[i
] == S1[j]
                 Min { F(i-1, j) + 1, F(i, j-1) + 1, F(i-1, j-1) + 1 }, S1[i
] != S1[j]

   注意： 动态规划初始化
   for (int i = 0; i <= len1; i++) {
            d[i][0] = i;
    }

4. Unique path
   F(i, j) = F(i-1, j) + F(i, j-1)

5. Longest Substring without Repeating Characters
   F(i) = F(i-1) + 1, S[i] doesn't appear before
         Min{ F(i-1) + 1, i - map.get(S[i]) }

6. Maximum sub-array
   F(i) = F(i-1) + A[i], F(i-1) > 0
        = A[i]             , F(i-1) <= 0

7. Palindrome 
    F(j)  = isPalindrome( i…j ) && F(i)
    P(i, j) = P(i+1, j-1) from bottom left corner

8. Minimal coins
    F(n) = Min{ F(n-a[i])}  i = 0…m (m coins)

9. Regular expression
    if(p[j] == '*')
        d(i, j) = d(i, j-2) || d(i, j-1) | d(i-1, j)

10. Interleave string
    a[i][j] = (a[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) 
         || (a[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));
--