前情提示：Go语言学习者。本文参考https://labuladong.gitee.io/algo，代码自己参考抒写，若有不妥之处，感谢指正

关于golang算法文章，为了便于下载和整理，都已开源放在：

涉及题目

动态规划问题（Dynamic Programming）应该是很多读者头疼的，不过这类问题也是最具有技巧性，最有意思的。本书使用了整整一个章节专门来写这个算法，动态规划的重要性也可见一斑。

本文解决几个问题：

动态规划是什么？解决动态规划问题有什么技巧？如何学习动态规划？

刷题刷多了就会发现，算法技巧就那几个套路，我们后续的动态规划系列章节，都在使用本文的解题框架思维，如果你心里有数，就会轻松很多。所以本文放在第一章，来扒一扒动态规划的裤子，形成一套解决这类问题的思维框架，希望能够成为解决动态规划问题的一部指导方针。本文就来讲解该算法的基本套路框架，下面上干货。

首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。

既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。

动态规划这么简单，就是穷举就完事了？我看到的动态规划问题都很难啊！

首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我来提供我研究出来的一个思维框架，辅助你思考状态转移方程：

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

按上面的套路走，最后的结果就可以套这个框架：

// 伪码 
//初始化 base case 
dp[0][0][...] = base case
//进行状态转移
for _,状态1 = range 状态1的所有取值{
    for _,状态2 = range 状态2的所有取值{
        for ...{
            dp[状态1][状态2][...] = 求最值(选择1， 选择2， ...)
        }
        
    }
}

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

一、斐波那契数列

请读者不要嫌弃这个例子简单，只有简单的例子才能让你把精力充分集中在算法背后的通用思想和技巧上，而不会被那些隐晦的细节问题搞的莫名其妙。想要困难的例子，历史文章里有的是。

1、暴力递归

斐波那契数列的数学形式就是递归的，写成代码就是这样：

func fib(n int) int {
    if n < 2{
        return n
    }
    return fib(n-1)+fib(n-2)
}

这个不用多说了，学校老师讲递归的时候似乎都是拿这个举例。我们也知道这样写代码虽然简洁易懂，但是十分低效，低效在哪里？假设 n = 20，请画出递归树：

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

f(20)f(19)f(18)f(19)f(18)f(17)f(1)f(2)

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

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

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

所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，爆炸。

f(18)f(18)f(18)

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

2、带备忘录的递归解法

明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。

func fib(n int) int {
    // 备忘录全初始化为0
    var memo []int = make([]int, n+1)
    // 进行带备忘录的递归
    return helper(memo,n)
}
func helper(memo []int, n int) int {
    // base case
    if n < 2{
        return n
    }
    // 已经计算过的，不用再计算了
    if memo[n]!=0{
        return memo[n]
    }
    return helper(memo,n-1) + helper(memo,n-2)
}

现在，画出递归树，你就知道「备忘录」到底做了什么。

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

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

f(1)f(2)f(3)f(20)

解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。

所以，本算法的时间复杂度是 O(n)。比起暴力算法，是降维打击。

至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。

f(20)f(1)f(2)
f(1)f(2)f(20)

3、dp 数组的迭代解法

有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算岂不美哉！

func fib(n int) int {
    if n ==0{
        return 0
    }
    var dp []int = 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)nnn - 1n - 2
return f(n - 1) + f(n - 2)dp[i] = dp[i - 1] + dp[i - 2]

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

这个例子的最后，讲一个细节优化。细心的读者会发现，根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：

func fib(n int) int {
    if n < 2{
        return n
    }
    //base case
    p,q,r := 0,0,1
    // 状态转移
    for i:=2; i<=n; i++{
        p = q
        q = r
        r = p + q
    }
    return r
}

n

有人会问，动态规划的另一个重要特性「最优子结构」，怎么没有涉及？下面会涉及。斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，以上旨在说明重叠子问题的消除方法，演示得到最优解法逐步求精的过程。下面，看第二个例子，凑零钱问题。

二、凑零钱问题

kc1, c2 ... ckamount
// coins中是可选硬币面值，amount是目标金额
func coinChange(coins []int, amount int) int {
}

k = 3amount = 11

你认为计算机应该如何解决这个问题？显然，就是把所有可能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。

1、暴力递归

首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？你肯定不想看数学证明，我用一个直观的例子来讲解。

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

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

但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，数学分数高，语文分数就会降低，反之亦然。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。

amount = 11amount = 10

PS：关于最优子结构的问题，后文 动态规划答疑篇 还会再举例探讨。

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

amount
amount

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

dpdpdp
dp(n)nn

搞清楚上面这几个关键点，解法的伪码就可以写出来了：

// 伪码框架
func coinChange(coins []int, amount int)int{
    // 定义：要凑出金额n，至少要dp(coins, n)个硬币
    func dp(n int) int{
        // 做选择，选择需要硬币最少的那个结果
        for _,coin = range coins{
            res = min(res, 1+dp(n-coin))
        }
        return res
    }
    //题目要求的最终结果是dp(amount)
    return dp(amount)
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

根据伪码，我们加上 base case 即可得到最终的答案。显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1：

// 此种方法，在leetcode提交会超出时间
func coinChange(coins []int, amount int)int{
    // 定义：要凑出金额n，至少要dp(coins, n)个硬币
    func dp(n int) int{
        // 做选择，选择需要硬币最少的那个结果
        for _,coin = range coins{
            res = min(res, 1+dp(n-coin))
        }
        return res
    }
    //题目要求的最终结果是dp(amount)
    return dp(amount)
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

coinChangedpdpdp

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

amount = 11, coins = {1,2,5}

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

子问题总数为递归树节点个数，这个比较难看出来，是 O(n^k)，总之是指数级别的。每个子问题中含有一个 for 循环，复杂度为 O(k)。所以总时间复杂度为 O(k * n^k)，指数级别。

2、带备忘录的递归

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

var memo[]int
func coinChange(coins []int, amount int)int{
    // 备忘录全初始化为0
    memo = make([]int, amount + 1)
    //初始化memo
    for i:=0;i<amount+1;i++{
        memo[i]=-666
    }
    return dp(coins,amount)
}
func dp(coins []int, amount int) int{
    if amount ==0 {return 0}
    if amount < 0{return -1}
    // 查备忘录，防止重复计算
    if memo[amount]!=-666{return memo[amount]}
    res := math.MaxInt32
    for _,coin := range coins{
        // 计算子问题的结果
        subProblem := dp(coins, amount-coin)
        // 子问题无解，则跳过
        if subProblem == -1{continue}
        // 在子问题中选择最优解，然后加1
        res = min(res, subProblem+1)
    }
    // 把计算结果存入备忘录
    if res == math.MaxInt32{
        memo[amount] = -1
    }else{
        memo[amount] = res
    }
    return memo[amount]
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

n

3、dp 数组的迭代解法

dpdpdpdp
dpidp[i]

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

func coinChange(coins []int, amount int) int{
    // dp 数组
    var dp []int = make([]int, amount+1)
    // 数组大小为amount+1,初始值也为amount+1
    for i, _ := range dp{
        dp[i] = amount+1
    }
    // base case
    dp[0] = 0
    // 外层for循环在遍历所有状态的所有取值
    for i:=1; i<len(dp); i++ { // 注意在这里不能使用range得到的值，可以使用索引，因为range遍历得到的值是未改变、最初的数组值
        //内层循环求所有选择的最小值
        for _, coin := range coins {
            //子问题无解 跳过
            if i - coin < 0 {
                continue
            }
            dp[i] = min(dp[i], dp[i-coin]+1)
        }
    }
    if dp[amount] == amount + 1{
        return -1
    }else{
        return dp[amount]
    }
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

dpamount + 1amountamountamount + 1Integer.MAX_VALUEdp[i - coin] + 1

三、最后总结

第一个斐波那契数列的问题，解释了如何通过「备忘录」或者「dp table」的方法来优化递归树，并且明确了这两种方法本质上是一样的，只是自顶向下和自底向上的不同而已。

第二个凑零钱的问题，展示了如何流程化确定「状态转移方程」，只要通过状态转移方程写出暴力递归解，剩下的也就是优化递归树，消除重叠子问题而已。

如果你不太了解动态规划，还能看到这里，真得给你鼓掌，相信你已经掌握了这个算法的设计技巧。

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

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

备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门，除此之外，试问，还能玩出啥花活？

之后我们会有一章专门讲解动态规划问题，如果有任何问题都可以随时回来重读本文，希望读者在阅读每个题目和解法时，多往「状态」和「选择」上靠，才能对这套框架产生自己的理解，运用自如。