Skip to main content

01F 动态规划

fib():递归​

f(n)=f(n-1)+f(n-2)

递推方程​

设f(n)为参数为n时的时间复杂度，很明显：f(n)=f(n-1)+f(n-2)，这就转化为了数学上的二阶常系数差分方程，并且为齐次方程。 即转化为了求f(n)的值，f(n)=f(n-1)+f(n-2)且f(0)=0; f(1)=1; 特征方程为：x^2-x-1=0。 得 x=(1±√5)/2。 即为黄金分阁数 Phi(大写Φ,小写φ)

复杂度为 O(Φ^n), 为指数复杂度。

封底估算​

Φ^36 = 2^25 Φ^5 = 10

fib(43) = 2^30 = 10^9 = 1秒, fib(67) = 1 day, fib(92) = 3 世纪

递归跟踪​

递归版fib()低效的根源在于,各递归实例均被大量地重复调用. 故可以改进为迭代记忆版，将已经计算过的结果制表备查。

动态规划​

由自顶而下递归,改为自底而上迭代。

f = 1; g = 0; //fib(-1), fib(0)
while ( 0 < n-- ) {
    g = g + f;
    f = g - f;
}
return g;

LCS：最长公共子序列​

子序列(Subsequence):由序列中若干字符,按原相对次序构成.
最长公共子序列(Longest Common Subsequence):两个序列公共子序列中的最长者.

减治递归​

对于序列A[0,n)和B[0,m),LCS(n,m)无非三种情况

  • 若n = 0或m = 0,则取作空序列("") //递归基
  • 若A[n-1] = 'X' = B[m-1],则取作:LCS(n-1,m-1) + 'X' //减而治之
  • A[n-1] != B[m-1],则在 LCS(n,m-1) 与 LCS(n-1,m) 中取更长者 //分而治之

分治递归​

略

理解​

LCS的每一个解,对应于(0,0)与(n,m) 棋盘之间的一条单调通路;反之亦然

复杂度​

最好情况,只需 O(n + m) 时间, 最坏情况,需要 Ω(2^n) 时间.

优化：递归记忆法

动态规划​

与fib()类似,这里也有大量重复的递归实例(子问题)。各子问题,分别对应于A和B的某个前缀组合，因此实际上,总共不过 O(n*m)种。

  • 将所有子问题(假想地)列成一张表
  • 颠倒计算方向:从LCS(0,0)出发,依次计算出所有项——直至LCS(n,m)