力扣力扣力：动态规划入门（1）

        相信大家在第一次学动态规划的时候都是一脸懵逼的，在看了很多题解之后，陷入到了空的“最优子结构”等的大词上，依旧看不懂动态规划到底在干什么。今天我们也是老样子再一次的从零开始学习与讲解，俺也是从零开始学动态规划，所以学多少写多少，和大家一起领悟动态规划最自然的想法。

我们为什么需要动态规划：

        在搞清楚动态规划怎么实现之前，我们先搞清楚我们为什么需要它。我们都知道在算法的世界里面，一般分为两种问题，一种是有确定算法流程，确定的计算过程，计算机按照代码顺序执行就一定能拿到结果的，例如图论里面的最小生成树、最短路径等算法；还有一种是我们拿不到这种确切的计算过程，所以我们只能按照一定的顺序一个个去试出我们想要的结果，例如经典的递归算法。

        这两种问题对应到数学问题中， 就好像一种是我们知道数列的通项公式，一种是我们知道了数列的递推式。例如最简单的通向公式等差数列：an = a1+(n-1)*d，又例如最经典的递推公式斐波那契数列：F(n) = F(n - 1) + F(n - 2)。动态规划要解决的问题就是后者，而后者大多都能用递归来解决，动态规划要干的事情就是用空间来储存递归过程中重复计算的子问题，来减少计算过程优化流程。所以只要是一个动态规划能解决的问题就一定对应着一个重复调用的递归子问题，动态规划能解决的递归也同样能够解决。实际上我们在进行流程优化的时候经常会利用上述缓存已经出现过的结果这种思想，在计算机网络、操作系统中等很多对时间要求高的地方可以看到这种操作。

ok，在简单了解之后我们做三道简单经典题目，来通过不断优化流程去逐步感受上述的思想。动态规划这类的算法题不在多在于弄懂原理，因为每一道题都不一样都得具体问题具体分析。

斐波那契数列：509. 斐波那契数 - 力扣（LeetCode）

这里我们就用上面给出的递推例子斐波那契额数列来直观感受递推思想的优化流程。

递归版：

我们先给出最常见的递归写法，相信大家这种应该都会。

class Solution {
public:
    int fib(int n) {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        return fib(n-1)+fib(n-2);
    }
};

我们以计算fib(4)小一点的数字来举例，下面给出递归的展开二叉树图

            fib(4)
           /       \
      fib(3)       fib(2)
     /      \       /     \
  fib(2)   fib(1) fib(1) fib(0)
 /      \
fib(1) fib(0)

这种递归的时间复杂度显然是O(2^N),接下来我们开始进行优化递归过程。

        首先我们可以发现，fib(2),fib(1),fib(0)这几个重复计算了好多次，这也就是我们上面说的重复计算的递归子问题，所以这里存在优化的空间。我们要想能不能直接储存起来之前算过的值，这样如果出现第二次多次计算的时候直接调用前面存起来的值不就好了。下面给出缓存后的二叉树展开图：

            fib(i)
           /       \
      fib(i-1)       fib(i-2)
     /      \            
  fib(i-2)   fib(i-3)
 /      \
fib(i-3) fib(i-4)
 /
fib(i-4)
...
...

        我们可以直观的发现我们其实只需要自底向上计算最左边的一列加上其右子树例如fib(i-3)和fib(i-4)，所以这个时候时间复杂度就很直观的降到了O(N)。这就是优化进步的地方，所以其实本质上干的事情就是拿空间的储存结构去换取时间上的复杂度优化。

        所以这里我们需要一个数据结构来储存计算过的值，我们在动态规划中一般称这种表为dp表。而我们接下来要做的事情就是填满这张表返回表的最后一个元素即可。所以在动态规划中最重要的一步就是知道dp表怎么来的表示什么意思，我们一般有以下几种方式：1.题目要求 2.经验+题目要求 3.分析问题的过程中，发现了重复的子问题。我们这道题由于比较简单题目直接给出了，其实按照上述分析也可以算发现重复子问题。

        其次才是最难的得出状态转移方程，也就是如何填上我们的这张表。由于本道题很简单，状态转移方程说人话就是求出递推式。这里题目也直接给出了就是F(n) = F(n - 1) + F(n - 2)。

        然后就是对表进行初始化过程，这个过程主要是用来保证不会越界访问。例如当n=0或者1的时候取到了-1和-2这种值就已经越界访问了。

动态规划版:

class Solution {
public:
    int fib(int n) {
        //1.创建dp表
        //2.初始化表
        //3.填表
        //4.返回值

        //先处理前两项情况
        if(n == 0) return 0;
        if(n == 1) return 1;

        vector<int> dp(n+1);//由于题目下标是从0开始，所以是n+1
        dp[0] = 0 , dp[1] = 1;
        for(int i=2;i<=n;i++)
            dp[i] = dp[i-1] + dp[i-2];
        return dp[n]; 
    }
};

ok我们现在已经对时间复杂度进行了很大的优化，算到这里还能不能进一步优化。

其实是能的，我们还可以对空间进行优化。我们在填表的时候会发现其实我们计算每一个格子的时候只利用到前两个，之前的都利用不到了。又由于我们只需要拿到最终结果也就是最后一个元素，所以前面格子的数据不需要保存。所以实际上我们只需要定义三个变量就能解决了，从原来的O(N)的空间复杂度进一步优化到O(1)常数级复杂度。这个方法也一般被称为滚动数组，在背包问题中会经常用到。

滚动数组版：

class Solution {
public:
    int fib(int n) {
        //1.创建dp表
        //2.初始化表
        //3.填表
        //4.返回值

        //先处理前两项情况
        if(n == 0) return 0;
        if(n == 1) return 1;

        int a = 0, b = 1, c = 0;
        for(int i=2;i<=n;i++)
        {
            //先计算下一个数
            c = a + b;
            //滚动操作
            a = b, b = c;
        }
        return c; 
    }
};

当然由于这道题是斐波那契额数列的特殊性，我们可以通过数学的方法得到通项公式，大多数题目是无法做到这一点的，这里我们不再过多讨论这种方法。

三步问题：面试题 08.01. 三步问题 - 力扣（LeetCode）

        关于这道题，首先我想说的一点是一般对于动态规划的题目我们从后往前思考。也就是如果我们想要计算n，是不是先要计算n-1，想要得到n-1是不是先要得到n-2。如果我们一上来按照正常人思考的模式从前往后数的话，前几个台阶还可以理清楚，到后面方法一多很容易数错，从而导致归纳错误。如果能数对的话，其实也可以通过找规律来得到状态转移方程。而从后往前计算从本质上是符合递归计算的顺序的，递归计算是自底向上计算得到的。

        在明确了思考方向后，我们就很容易得到思路，想要到第n阶台阶，前一步有三种可能性，即：前一步已经到达第n-1、n-2、n-3阶台阶三种可能，至于为什么是三种其实是因为小孩一次只能最大跳3阶，如果是4或者5阶我们也可以同步进行变化。下面给出实现：

class Solution {
public:
    int waysToStep(int n) {
        if(n==1 || n==2) return n;
        if(n==3) return 4;
        const int MOD = 1e9+7;
        vector<int> dp(n+1);
        dp[1] = 1,dp[2] = 2,dp[3] = 4;
        for(int i=4;i<=n;i++)
            dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;
        return dp[n];
    }
};

唯一需要注意的是这道题由于数字可能会很大需要%一下mod

最小花费爬楼梯：LCR 088. 使用最小花费爬楼梯

我们还是一样的从后往前分析，如果要爬完楼梯，由于一次只能爬一到两步，那么前一步就只有两种可能，一种是离楼顶只有一阶台阶，还有一种是两阶。

那么爬到楼顶的最小花费就是这两种方法中的小的那个。

dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])：到达前一步再加上最后一步的花费即可。

版本一：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
         vector<int> dp(n+1);
        for(int i=2;i<=n;i++)
            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        return dp[n];
    }
};

与之前不同的是，这道题似乎没有初始化数组，这是因为这道题初始化dp[0]=0，dp[1]=0,而调用vector的构造函数会自动填上0，所以省去这一步。

版本二：

        版本一的dp[i]的含义是到i位置的最小花费，所以顾名思义就是以i为终点的最小花费，这里我们再介绍另一种以i为起点到台阶顶的最小花费。和前面一样还是只分为两种可能：

所以还是一样，最小花费依旧是这二者的min。另外这里的初始化也要从最后两个格子开始初始化，初始化的值就为该位子的cost，其次填表的顺序也要相同的从后往前开始填。最后给出实现：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];
        for(int i=n-3;i>=0;i--)
            dp[i] = cost[i]+min(dp[i+1],dp[i+2]);
        return min(dp[0],dp[1]);
    }
};