动态规划

Make it work \
Make it right - 递归
Make it fast - 迭代
– Kent Beck

动态规划: 通过递归找出算法本质，并且给出了初步解，再讲其等效成迭代形式

int fib(int n) {
  return (2 > n) ? n : fib(n-1) + fib(n-2);
}

work, right, but not fast.

封底估算

$^36 = 2^25, ==> $^43 = 2^30 = (2^10)^3 = 10^9 flo = 1sec
$^5 = 10, ==> $^67 = 10^14 flo = 10^5 sec = 1 day

递归跟踪

效率低的原因是递归实例被重复调用。

解决方法A(记忆:memoization)

int fib_memoization(int n, int mem_lst[]) {
  // 将已经计算的结果, 制成表备查
  if (is_exist(mem_lst[n])) {
    return mem_lst[n];
  } else {
    if (2 > n) {mem_lst[n] = n;} else {
      mem_lst[n] = fib_memoization(n-1, mem_lst) +
          fib_memoization(n-2, mem_lst);
      return mem_lst[n];
    }
  }
}

解决方法B 动态规划
上楼梯。


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

不太能理解, 先放着

最长公共子序列

子序列(Subsequence): 有序列中若干字符，按原相对次序构成

最长公共子序列(Longest common subsequence)，两个序列公共子序列的最长者

可能有多个，可能有歧义

实现

暂时还实现不了

动态规划

理解了一下，方法上有差异，思想上为自下而上的求解，有那么点在gh中做的时候的思想在里面。