知道释迦牟尼是怎么来的吗？<转载># Joke - 肚皮舞运动
r*m
1 楼
有朋友提到不知道怎么做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));
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));
