Dynamic Programming，动态规划

笔记和理解DP:

• memorize (remember) and reuse solutions to subproblems that help to solve our original problem. (recursion + memorization)

• Guess! We don't know the answer? Guess and try all guesses! And then take the best one.

• Subproblems dependencies should be acyclic. （subproblem相互之间的依赖不能出现循环。）

1. DP: "careful brute force".

2. DP: guessing + recursion + memorization

3. DP: shortest path in some DAG

4. time = #subproblems * (time / subprobelm) and we treat recursively calls as O(1).

**5 "easy" steps to DP:

1. define subproblem**

2. count the number of subproblems

   • guess(part of solutions)

3. count the number of choices - how many different possibilities are there

   • relate all subproblem solutions with each other

4. for Fibonacci number, we use fib(k) = f(k - 1) + f(k - 2)

5. for some other examples, we try all the possibilities and get the min or max result.

   • build an algorithm (bottom-up approach or recursion + memorization)

6. check the subproblem is acyclic, which means there is a topological sort order

   • solve the original problem

最简单的例子，计算斐波那契数。

public int fib(int n) {
  if (n == 1 || n == 2) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}

这个function的时间复杂度是指数级别的，然后我们可以想到用一些数据结构，比如array，比如hashmap，去把中间的结果存下来，对于fib(i)来说，我们可能访问多次，但是真正的搜索只进行一次。因此，我们可以认为我们把时间复杂度降到了O(n)。

public int fib(int n, Map<Integer, Integer> map) {
  // assume the map we have, initialized with map(1, 1) and map(2, 1).
  if (map.containsKey(n)) {
    return map.get(n);
  }

  return fib(n - 1, map) + fib(n - 2, map);
}

Memorizatoin是一种top-down的思考方式，当然我们也可以bottom-up的做。

public int fib(int n) {
  if (n == 1 || n == 2) {
    return 1;
  }

  int[] dp = new int[n + 1];
  dp[1] = 1;
  dp[2] = 1;

  for (int i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

这个bottom-up的写法，另外有一个好处是可以优化空间。在这道题里，fib(k)其实只和fib(k - 1)还有fib(k - 2)有关，所以我们可以把空间优化到constant space。

public int fib(int n) {
  if (n == 1 || n == 2) {
    return 1;
  }

  int[] dp = new int[2];
  dp[0] = 1;
  dp[1] = 1;

  for (int i = 3; i <= n; i++) {
    int index = (i - 1) % 2;
    dp[index] = dp[0] + dp[1];
  }
  return dp[(n - 1) % 2];
}