// 斐波那契数列 - 递归
// fib(n) = fib(n - 1) + fib(n -2)
int fib(n) {
return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}
T(0) = T(1) = 1, T(n) = T(n - 1) + T(n - 2) + 1
T(n) = O(fib(n + 1)) = O(2n)
各递归实例被大量重复调用,导致算法低效
记忆(memoization):将已计算实例的结果制表备查
动态规划(dynamic programming):颠倒计算方向,自顶而下递归,自底而上迭代
// 斐波那契数列 - 动态规划
int fib(n) {
f = 0;
g= 1;
while (0 < n--) {
g = g + f;
f = g - f;
}
return g;
}
T(n) = O(n)
子序列(subsequence),由序列中若干字符(元素),按原相对次序构成。
最长公共子序列(LCS, longest common subsequence),两个序列公共子序列中最长者。
递归
对于序列A[0, n]与序列B[0, m],LCS(A, B)有3种情况:
0) 若n = -1或m = -1,则取作空序列("")
1) 若A[n] = B[m] = 'X',则取作LCS(A[0, n), B[0, m)) + 'X'
2) 若A[n] ≠ B[m],则取LCS(A[0, n], B[0, m))与LCS(A[0, n), B[0, m])较长者
迭代
0/) 将所有子问题列成一张表
1/) 颠倒计算方向,从LCS(A[0], B[0])开始依次计算所有项
public int longestCommonSubsequence(String text1, String text2) {
if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) return 0;
char[] chas1 = text1.toCharArray();
char[] chas2 = text2.toCharArray();
int m = chas1.length, n = chas2.length;
int[][] dp = new int[m][n];
dp[0][0] = chas1[0] == chas2[0] ? 1 : 0;
for (int i = 1; i < m; i++) dp[i][0] = chas1[i] == chas2[0] ? 1 : dp[i - 1][0];
for (int j = 1; j < n; j++) dp[0][j] = chas1[0] == chas2[j] ? 1 : dp[0][j - 1];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (chas1[i] == chas2[j]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
return dp[m - 1][n - 1];
}
网友评论