1.4 动态规划

// 斐波那契数列 - 递归
// 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(2ⁿ)
各递归实例被大量重复调用，导致算法低效

记忆(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];
}