动态规划是什么？解决动态规划问题有什么技巧？如何学习动态规划？
刷题刷多了就会发现，算法技巧就那几个套路，我们后续的动态规划系列章节，都在使用本文的解题框架思维，如果你心里有数，就会轻松很多。所以本文放在第一章，来扒一扒动态规划的裤子，形成一套解决这类问题的思维框架，希望能够成为解决动态规划问题的一部指导方针。本文就来讲解该算法的基本套路框架，下面上干货。
首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。
既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。
动态规划这么简单，就是穷举就完事了？我看到的动态规划问题都很难啊！
首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。
以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我来提供我研究出来的一个思维框架，辅助你思考状态转移方程：
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
按上面的套路走，最后的结果就可以套这个框架：

  1. # 初始化 base case
  2. dp[0][0][...] = base
  3. # 进行状态转移
  4. for 状态1 in 状态1的所有取值：
  5.     for 状态2 in 状态2的所有取值：
  6.         for ...
  7.             dp[状态1][状态2][...] = 求最值(选择1，选择2...)

509. 斐波那契数

难度简单290
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

暴力破解法

  1. class Solution {
  2.     public int fib(int n) {
  3.         if(n==0){
  4.             return 0;
  5.         }
  6.         if(n==1||n==2){
  7.             return 1;
  8.         }
  9.         return fib(n-1)+fib(n-2);
  10.     }
  11. }

image.png
解析
image.png
这个递归树怎么理解？就是说想要计算原问题 f(20)，我就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。
观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。
这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。

使用备忘录：

  1. class Solution {
  2.     public int fib(int n) {
  3.         //备忘录全初始化为0
  4.         int []memo=new int [n+1];
  5.         //进行带备忘录的递归
  6.         return build(memo,n);
  7.     }
  8.     public int build(int[]memo,int n){
  9.         //base case
  10.         if(n==0||n==1){
  11.             return n;
  12.         }
  13.         //已经计算过，不用再次计算了
  14.         if(memo[n]!=0){
  15.             return memo[n];
  16.         }
  17.         memo[n]=build(memo,n-1)+build(memo,n-2);
  18.         return memo[n];
  19.     }
  20. }

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

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

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

  1. class Solution {
  2.     public int fib(int n) {
  3.        if(n==0){
  4.            return 0;
  5.        }
  6.        int []dp =new int [n+1];
  7.        //base case
  8.        dp[0]=0;
  9.        dp[1]=1;
  10.        //状态转移
  11.        for (int i=2;i<=n;i++){
  12.            dp[i]=dp[i-1]+dp[i-2];
  13.        }
  14.        return dp[n];
  15.     }
  17. }

image.png
有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算岂不美哉！
image.png
这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：
image.png

为啥叫「状态转移方程」？其实就是为了听起来高端。你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移，仅此而已。

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

  1. class Solution {
  2.     public int fib(int n) {
  3.        if(n==0){
  4.            return 0;
  5.        }
  6.       int pre=1;
  7.       int cur=1;
  8.        //状态转移
  9.        for (int i=3;i<=n;i++){
  10.           int sum=cur+pre;
  11.           pre=cur;
  12.           cur=sum;
  13.        }
  14.        return cur;
  15.     }
  17. }

image.png
这个技巧就是所谓的「状态压缩」，如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据，上述例子就相当于把DP table 的大小从 n 缩小到 2。后续的动态规划章节中我们还会看到这样的例子，一般来说是把一个二维的 DP table 压缩成一维，即把空间复杂度从 O(n^2) 压缩到 O(n)。
有人会问，动态规划的另一个重要特性「最优子结构」，怎么没有涉及？下面会涉及。斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，以上旨在说明重叠子问题的消除方法，演示得到最优解法逐步求精的过程。下面，看第二个例子，凑零钱问题。