第三章 动态规划

基本思想：将待求解问题分解为若干子问题。子问题通常不独立，如果使用分治，子问题数目过多

动态规划算法适用于解最优化问题。

（1）找出最优解的性质，并刻画其结构特征。

（2）递归地定义最优值。

（3）以自底向上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解

动态规划流程：

递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法。

例一：斐波那契数列

步骤一：递归（暴力解决）

def fib(n):
	if n==1 or n==2:
		return 1
	return fib(n-1)+fib(n-2)

缺点：低效

递归树：

T(n) = O(2^n)

存在大量重复计算.

-->重叠子问题

步骤二：带备忘录的递归算法

创造一个备忘录-->记录计算过的子问题答案，后续无需重复计算，直接从备忘录读取。

可以使用一个数组或哈希表。

带备忘录的递归算法，把一棵存在巨量冗余的递归树通过剪枝，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。此时：

T(n) = O(n)

这种方法实际上是从上向下的问题，从一个规模较大的原问题比如说 f(10)，向下逐渐分解规模，直到 f(1) 和 f(2) ，然后逐层返回答案.

而动态规划问题，是一种自下向上的问题。直接从最底下，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(10)，这就是动态规划的思路，从而动态规划一般都脱离了递归，而是由循环迭代完成计算。

步骤三：动态规划

可以把“备忘录”独立成一个表：dp

int fib(int N) {
  vector<int> dp(N + 1, 0);
  dp[1] = dp[2] = 1;
  for (int i = 3; i <= N; i++)
    dp[i] = dp[i - 1] + dp[i - 2];
  return dp[N];
}

状态转移方程

把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来。

上操作：

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

dp[i] = dp[i - 1] + dp[i - 2]

对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。

那么：根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，此时dp数组可以更加简化：

int fib(int n) {
    if (n < 2) return n;
    int prev = 0, curr = 1;
    for (int i = 0; i < n - 1; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

空间复杂度为：O(1)

此时，我们涉及到动态规划中的重叠子问题和状态转移方程

例二：凑零钱问题

给出k 种面值的硬币，面值分别为 c1, c2 ... ck，再给出总金额 n，问最少需要几枚硬币凑出这个金额，如果不可能凑出，则返回 -1 。

如，k = 3，面值分别为 1，2，5，总金额 n = 11，那么最少需要 3 枚硬币，即 11 = 5 + 5 + 1 。

首先可以写出该问题的状态转移方程：

其中：n表示目标余额，Ci为硬币的面值。

在该问题中：原问题的解由子问题的最优解构成，且子问题之间相互独立。

最优子结构

解法：

• 暴力解法

  def coinChange(coins, amount):
      if amount == 0:
          return 0
      ans = float('inf')
      for coin in coins:
          if amount - coin < 0:
              continue
          subProb = coinChange(coins, amount - coin)
          if subProb == -1:
              continue
          ans = min(ans, subProb + 1)
      return ans if ans != float('inf') else -1
  
  

• 备忘录递归

  def coinChange(coins, amount):
      memo = {}
      def helper(amount):
          if amount in memo:
              return memo[amount]
          if amount == 0:
              return 0
          if amount < 0:
              return -1
          ans = float('inf')
          for coin in coins:
              subProb = helper(amount - coin)
              if subProb == -1:
                  continue
              ans = min(ans, subProb + 1)
          memo[amount] = ans if ans != float('inf') else -1
          return memo[amount]
  
      return helper(amount)
  

• 动态规划

  def coinChange(coins, amount):
      dp = [amount + 1] * (amount + 1)
      dp[0] = 0
      for i in range(1, amount + 1):
          for coin in coins:
              if i - coin >= 0:
                  dp[i] = min(dp[i], 1 + dp[i - coin])
      return dp[amount] if dp[amount] != amount + 1 else -1
  

总结

如何穷举-->如何更好穷举

计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。

列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。

备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门。

相关链接

部分内容可能涉及到文章：
动态规划详解 (qq.com)