动态规划框架思路 | 顾澜的技术小站

动态规划的特点与解题思路

动态规划是一个运筹学上的一个最优化算法，所以动态规划问题一把都是求最值，比如让你求最长递增子序列，最小编辑距离等。

这类求最值的问题，他的核心是什么？其核心一定是穷举。因为要求最值，所以肯定要把所有的答案穷举出来，在其中找出最值。

虽然穷举听起来很简单，但是也不能小看他。动态规划问题一般都比较复杂，需要你熟练掌握递归。动态规划的三要素**「重叠子问题」，「状态转移方程」，「最优子结构」，其中「状态转移方程」最为关键，只有写出正确的「状态转移方程」，才可以正确的穷举。「重叠子问题」与「最优子结构」可以算是特性，我发现这个问题存在「重叠子问题」且具备「最优子结构」，那么这就是一个动态规划问题。动态规划存在「重叠子问题」**，在穷举时效率会很低，我们需要使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

这里提供一个思维框架，辅助你思考状态转移方程：

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

按照上面的思路，最后的解法代码就会是如下的框架：

// 自顶向下递归的动态规划
func dp(状态1， 状态2...) 最值 {
    for 选择 := range 所有可能的选择 {
        result = 求最值(result, dp(状态1, 状态2, ...))
    }
    return result
}

// 自底向上迭代的动态规划
// 初始化 base case
dp[0][0][...] = base case
// 进行状态转移
for 状态1 := range 状态1的所有取值：
    for 状态2 := range 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

后续通过斐波那契数列问题和凑零钱问题来详解动态规划的基本原理，前者主要是让你明白什么是重叠子问题（斐波那契数列没有求最值，所以严格来说不是动态规划问题），后者主要举集中于如何列出状态转移方程

509. 斐波那契数

1. 暴力递归解法

题目中就直接给出了递归公式，直接套用即可

func fib(n int) int {
    if n == 0 || n == 1 {
        return n
    }
    return fib1(n-1) + fib1(n-2)
}

上述代码简单易懂，但却十分低效，为什么低效，我们假设n=20，画出递归树：

PS：但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。

从上图的递归树种可知，要求出f(20)，我们要先计算出子问题f(18)和f(19)，我们要计算f(19)，我就要先计算出f(18)和f(17)，以此类推，最后遇到f(1)或者f(2)的时候，停止递归。

上述解法的时间复杂度为o(2^n)，指数级别。

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。

首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。

然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。

所以，这个算法的时间复杂度为二者相乘，即 O(2^n)

重新观察递归树很明显就能发现低效原因：存在大量的重复计算，比如图中的f(18)和f（17)都被计算了两次，而且以f(18)和f(17)为跟的这个递归树体量巨大，多算一遍，就会消耗巨大的时间，而且这个重复还指数级的。

这就是动态规划问题的第一个性质：「重叠子问题」。下面，我们想办法解决这个问题

2. 带备忘录的递归解法

明确了问题，其实我们就已经把问题解决了一半。居然耗时的原因是因为重复计算，那解决重复计算即可，采用上文提到的「备忘录」来优化即可。首先创造一个备忘录，每次计算完子问题的答案先放入备忘录再返回，每次需要计算一个子问题时，先去备忘录里查一查，存在则不需要重复计算。

一半使用数组和哈希表来充当这个备忘录，他们思路一样。使用数组是需要额外申请一个多余空间，因为数组下标从0开始的

func fib(n int) int {
    // 初始化备忘录
    memo := make([]int, n+1)
    return helper(n, memo)
}

func helper(n int, memo []int) int {
    if n == 0 || n == 1 {
        return n
    }
    // 判断是否计算过
    if memo[n] != 0 {
        // 已经计算过了
        return memo[n]
    }
    memo[n] = helper(n-1, memo) + helper(n-2, memo)
    return memo[n]
}

再次画出递归树

实际上，带「备忘录」的递归算法，就是把一颗巨量赘余的递归树进行修剪，把冗余的部分全部去掉，极大的减少了子问题的个数。

此时算法的时间复杂度为o(n)，相比与上面的，完全不在一个级别。

此时带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。但是与动态规划还是有区别，因为这种解法是「自顶向下」进行「递归」，常见的动态规划是「自底向上」进行「递推」。

何为「自顶向下」？观察上面我们画的递归树，是从上向下延伸，都是从一个规模较大的原问题比如f(20)向下逐渐分解规模，到直到 f(1) 和 f(2) 这两个base case，然后逐层返回答案，

那么「自底向上」呢？反过来，我们从底下、最简单、问题规模最小、已知结果的f(1) 和 f(2) 这两个base case开始往上推，直到推到我们想要的答案 f(20)。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。

3. 使用`dp`数组的迭代(递推)解法

根据上一步「备忘录」的启发，我们可以把这个「备忘录」独立成一个表，同城叫做「DP table」，在这张表上完成「自底向上」的「递推」。

func fib(n int) int {
    if n == 0 {
        return 0
    }
    dp := make([]int, n+1)
    // 初始化 base case
    dp[0], dp[1] = 0, 1
    for i := 2; i <= n; i++ {
        // 状态转移
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

通过上图可以发现这个「DP table」特别像上面那个修剪后的递归树，只是顺序反过来了。实际上，带备忘录的递归解法中的「备忘录」，就是动态规划中的「DP table」，这两个解法是差不多的，大部分情况下，效率也基本相同。

此时我们引出**「状态转移方程」**这个名词，实际上就是描述问题结构的数学形式：

$f(n) = \begin{cases} 1,n=1,2\\ f(n-1)+f(n-2),n>2 \end{cases}$

f(n)的函数参数会不断的变化，所以你把参数n想想要的一个状态，这个状态n是由状态n - 1和n - 2转移（相加）而来，仅此而已。

上面几种解法中的所有操作，例如return fib(n-1) + fib(n-2)，dp[i] = dp[i-1] + dp[i-2]，以及对「备忘录」或「DP table」的初始化操作，都是威少这个方程式的不同表现形态，有此可见列出「状态转移方程」的重要性，它是解决问题的核心，而且很容易发现，其实状态转移方程直接代表着暴力解法。

千万不要看不起暴力解法，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。只要写出暴力解，优化方案无非是备忘录或DP table。

4. 细节优化

根据菲波那切数列的状态转移方程，当前状态只和之前两个状态有关，那么我们就不需要那么长一个DP table来存储所有的状态，只需存储前两个状态即可，根据此思路，进一步优化，把空间复杂度降为0(1)

func fib4(n int) int {
    if n == 0 || n == 1 {
        return n
    }
    prev, curr := 0, 1
    for i := 2; i <= n; i++ {
        // 状态转移
        //dp[i-1], dp[i] = dp[i], dp[i-1] + dp[i-2]
        prev, curr = curr, prev+curr
    }
    return curr
}

这一般是动态规划问题的最后一步优化，如果我们发现状态转移只需要DP table中的一部分，那么可以尝试缩小DP table的大小，只记录必要的数据，降低空间复杂度。上述例子就相当于把DP table的大小从n降到了2。

此题并没有涉及动态规划的另一个重要特性「最优子结构」，因为菲波那切数列严格莱索不算动态规划，因为没有涉及到求最值，上文旨在说明重叠子问题的消除方法，演示的到最优解法的逐步优化过程。

322. 零钱兑换

1. 暴力递归

首先这个问题是动态规划问题，因为它具有「最优子结构」。要符合**「最优子结构」**，子问题必须互相独立。什么是相互独立？我们用一个简单且直观的例子来说明。

比如说，假设你考试，每门科目的成绩都是互相独立的。你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。

得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，「每门科目考到最高」这些子问题是互相独立，互不干扰的。

但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，不能同时达到满分，数学分数高，语文分数就会降低，反之亦然。

这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为「每门科目考到最高」的子问题并不独立，语文数学成绩户互相影响，无法同时最优，所以最优子结构被破坏。

回答凑零钱问题，为什么说它符合最优子结构呢？假设你有面值为1,2,5的硬币，你想求amount = 11 时的最少硬币数，如果你知道凑出amount = 10, 9, 6的最少硬币数（子问题），你只需要把子问题的答案+1（再选一枚面值为1, 2, 5的硬币），求个最小值，就是原问题的答案，因为硬币数量没有限制，所以子问题没有相互限制，是互相独立的。

那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？

1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。

所以我们可以这样定义 dp 函数：dp(n) 表示，输入一个目标金额 n，返回凑出目标金额 n 所需的最少硬币数量。

根据定义写成代码：

func coinChange(coins []int, amount int) int {
    return dp(coins, amount)
}

// 要凑出金额 n，至少要 dp(coins, n) 个硬币
func dp(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }
    if amount < 0 {
        return -1
    }
    res := math.MaxInt
    for _, coin := range coins {
        // 计算子问题的结果
        number := dp(coins, amount-coin)
        // 子问题无解则跳过
        if number == -1 {
            continue
        }
        // 在子问题中选择最优解，然后加一
        if res > number {
            res = number
        }
    }
    if res == math.MaxInt {
        return -1
    }
    return res + 1
}

PS：这里coinChange和dp函数签名完全一样，为了后文方便讲解，额外写一个dp函数来实现主逻辑

至此，状态转移方程其实已经完成了，以上算法已经是暴力解法了，以上代码的数学形式就是状态转移方程：

$dp(n) = \begin{cases} 0,n=0\\ -1,n<0\\ \min\lbrace dp(n - coin) + 1 | coin \in coins\rbrace, n > 0 \end{cases}$

至此，这个问题其实就解决了，只不过需要消除一下重叠子问题，比如 amount = 11, coins = {1,2,5} 时画出递归树看看：

递归算法的时间复杂度分析：子问题总数 x 解决每个子问题所需的时间

假设目标金额为 n，给定的硬币个数为 k，那么递归树最坏情况下高度为 n（全用面额为 1 的硬币），然后再假设这是一棵满 k 叉树，则节点的总数在 k^n 这个数量级。

接下来看每个子问题的复杂度，由于每次递归包含一个 for 循环，复杂度为 O(k)，相乘得到总时间复杂度为 O(k^n)，指数级别。

2.带备忘录的递归

类似之前斐波那契数列的例子，只需要稍加修改，就可以通过备忘录消除子问题

func coinChange1(coins []int, amount int) int {
    memo = make([]int, amount+1)
    for i, _ := range memo {
        // 备忘录初始化为一个不会被取到的特殊值，代表还未被计算
        memo[i] = -2
    }
    return dp1(coins, amount)
}

func dp1(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }
    if amount < 0 {
    return -1
    }
    // 查备忘录，防止重复计算
    if memo[amount] != -2 {
        return memo[amount]
    }
    res := math.MaxInt
    for _, coin := range coins {
        // 计算子问题的结果
        number := dp1(coins, amount-coin)
        // 子问题无解则跳过
        if number == -1 {
            continue
        }
        // 在子问题中选择最优解，然后加一
        if res > number {
            res = number
        }
    }
    // 把计算结果存入备忘录
    if res == math.MaxInt {
        memo[amount] = -1
        return -1
    } else {
        memo[amount] = res + 1
    }
    return memo[amount]
}

使用「备忘录」大大减小了子问题数目，完全消除了子问题的赘余，所以子问题的总数不会超过金额数n，即子问题数目为O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。

3. dp 数组的迭代解法

同样，我们可以自底向上使用「DP table」来消除重叠子问题，关于「状态」「选择」和「base case」与之前没有什么区别，dp数组的定义和刚才的dp函数类似，也是把「状态（金额）」作为变量，不过dp函数体现在函数参数，dp数组体现在数组索引：

dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出

根据我们文章开头给出的动态规划代码框架可以写出如下解法：

func coinChange2(coins []int, amount int) int {
    // 数组大小为 amount + 1，初始值也为 amount + 1
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0
    // 外层 for 循环在遍历所有状态的所有取值
    for i := 0; i <= amount; i++ {
        // 内层 for 循环在求所有选择的最小值
        for _, coin := range coins {
            // 子问题无解，跳过
            if i-coin < 0 {
                continue
            }
            // dp[i-coin] == dp(coins, amount-coin)
            if dp[i] > dp[i-coin] {
                dp[i] = dp[i-coin] + 1
            }
        }
    }
    if dp[amount] == amount+1 {
        return -1
    }
    return dp[amount]
}