解锁动态规划的奥秘：从零到精通的创新思维解析（2）

解锁动态规划的奥秘：从零到精通的创新思维解析（2）

前言：

小编在前几日讲述了关于动态规划的题目，今天小编继续进行动态规划相关题目的书写，动态规划的题目相较于小编之前讲述的习题难度是蛮大的，希望各位可以克服困难，最终掌握动态规划的题，下面就进入本文的讲题环节。

正文：

1.三步问题

1.1.题目来源

本题和之前的题目一样，同样都是来自于力扣，下面给出出处：面试题 08.01. 三步问题 - 力扣（LeetCode）

1.2.题目解析

本题其实就是上一个题目的翻版，具体题目可以看小编之前写的文章，由于本文写的比较早，我就不放链接了，本题其实就是告诉我们一个小孩上台阶的方法，分别是可以向上爬一阶，两阶，三阶，并且给出我们台阶的阶数，让我们去求解小孩爬台阶的方法，很像之前我们写过的泰波那契数的求解方法，不过此题还是和上题有着一点区别的，相信各位看完我的思路讲解以后，就知道本题和之前题目的区别，下面开始本题的思路讲解。

1.3.思路分析

对于动态规划的题目，我们还是分五步进行操作的：1.状态分析；2.状态转移方程；3.初始化；4.填表顺序；5.返回值。当然，我们还是需要建立一个dp表来记录数据

1.状态分析

对于本题的状态分析，我们可以通过经验+题目分析的方法来做出来，对于经验，我们通常是把i位置作为初始位置或者最后位置进行分析的，小编对于本题的解析就是从最后位置进行分析的，所以通过此经验，我们可以得知，dp[i]表示的是到达i位置的方法有几种，我们可以此时的状态分析出本题目的状态转移方程。

2.状态转移方程

本题目就是求出dp[I]到底等于什么，这个有的题目需要我们用状态机分析，不过状态机一般分析多状态的问题，本题目的状态单一，并且通过题目讲述我们自然而然的就知道了本题目的状态转移方程的书写，如下所示：

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

3.初始化

我们在写完状态转移方程后，我们就要关心我们写的状态转移方程的初始化问题了，本题和之前的问题一样，我们需要填写dp[1],dp[2]，dp[3]的数据，此时我们通过自己的推敲，就可以很快得出此时这三个位置的数分别是什么，前两个分别就和他们位置相同，第三个有四种走法，例题就告诉了我们，具体方法可以自己去求解，由于难度不大，小编就不写了（不知晓的读者朋友可以私信询问我）。

4.填表顺序

由于此时我们需要用到前面位置的数据，所以我们填表的顺序自然是从左到右。

5.返回值

由于此时是想求解第n个台阶的上去的方法，所以我们自然要返回dp[n]。

此时我们就完成了本题目的思路讲解，下面我们进入代码书写部分。

1.4.代码书写

首先，我们需要先判断此时给定我们的n是否是大于三的，如果此时的n在1到3为止的话，那么此时我们直接返回该位置的结果就行，避免数组越界。

if(n == 1 || n == 2) return n;
if(n == 3) return 4;

之后我们就可以创界一个dp表了，由于此时我们返回的是第n个位置的数据，所以dp表的创建自然也是要多创建一个位置了，创建完dp表以后，我们就要先进行特殊位置的初始化操作了。

vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;

之后我们就可以通过循环的方式对于dp表进行填写，此时我们可以从第四个位置进行填表操作，到达n位置即可，循环的内容自然是我们状态转移方程，只不过本题有个小坑，此时n的范围会很大，所以我们在填表的时候，可能会出现数太大导致一系列不可预估的风险，所以我们可以通过一个巧妙的取模操作进行代码的优化。之后我们返回第n个位置所对应的dp即可。

for(int i = 4 ; i <= n ; i++)
dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
return dp[n];

1.5.代码的优化

此时我们完全可以和上题一样通过滚动数组来对本题目的优化，只不过小编建议各位滚动数组在我们刷题的时候可以少用，因为它比较耗费时间，我们可以在以后算法比赛中或者企业的笔试中使用滚动数组优化我们的代码，我们日常联系大致练练就好，所以本题目我就不详细解释如何用滚动数组来进行本题目的优化了，不知晓如何使用的可以私信小编，小编会及时解释。

1.6.代码展示

1.优化前的代码

class Solution {
public:
    const int MOD = 1e9 + 7;
    int waysToStep(int n) {
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;
        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];
    }
};

2.优化的代码

class Solution {
public:
    const int MOD = 1e9 + 7;; //最大的数
    int waysToStep(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;
        int a = 1,b = 2,c = 4,d = 0;
        for(int i = 4 ; i <= n ; i++)
        {
            d = ((a + b) % MOD + c) % MOD;   //避免溢出，所以要取模
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
};

2.使用最小花费爬楼梯

2.1.题目来源

本题目也是来自于力扣，下面小编给出出处：746. 使用最小花费爬楼梯 - 力扣（LeetCode）

2.2.题目解析

本题目其实就是一个很简单的斐波那契数列模型，和上面的题目也是很像的，只不过上面是求解的方法，本题目是求解的最小花费，并且本题目也是可以选择向上爬一阶或者两阶楼梯，此时我们是要选择一种方法，此时的方法可以让我们在达到楼梯顶部的时候花费最小，此时我们需要考虑清楚，此时的楼梯顶部到底是哪里，就以上面的示例一为例，其实20并不是此时的顶部，它的上面一个元素才是真正意义上的楼梯顶部，这个各位要理解好，它事关我们之后的返回值的填写，下面我们进入本题目的思路讲解。

2.3.思路讲解

对于动态规划的题目，我们依旧可以分为五步进行分析，分别是：1.状态表示；2.状态转移方程；3.初始化；4.填表顺序；5.返回值。当然，我们肯定是需要构建一个dp表来实现上述操作。

1.状态表示

一般对于动态规划的状态表示，我们都是从经验+题目分析入手的，一般的经验都是以i位置为开头或者结尾，然后巴拉巴拉（题目分析），此题我们可以以i位置为结尾进行分析，所以此时的dp[i]表示到达i位置的最小花费，之后我们可以根据dp[i]进行状态转移方程的书写。

2.状态转移方程

对于状态转移方程，我们无非就是根据最近一步来划分问题，简单来说，我们可以从dp[i]的前后入手，来推导出dp[i]，至于是从前分析还是从后面分析，这取决于此时dp[i]表示什么，以本题为例，dp[i]表示到达i位置时候的最小花费，所以此时我们可以从前面来推导出dp[i]，此时我们从题目分析，发现此时我们可以从之前的台阶或者前两个台阶来到达当前台阶，所以此时我们可以通过dp[i - 1]或者dp[i - 2]来得到此时的dp[i]，我们可以求出它们的最小值，然后在加上它们位置的花费来达到最小花费，其方程如下所示：

dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]) ;

3.初始化

在写完状态转移方程以后，就要开始处理细节问题了，首先自然就是初始化的问题，本题的初始化自然也是很快就可以想到的，自然是dp[0]和dp[1]，通过题目分析，我们可以知道此时可以从0位置或者1位置上台阶，所以它俩自然是0。

4.填表顺序

由于此时的dp[i]需要用到前面的顺序，所以本题自然也是从左到右依次填表。

5.返回值

由于本题是需要最后一阶的位置，所以自然也是需要返回dp[n]的。

2.4.代码编写

首先，我们还是和之前题目一样，需要先判断此时台阶的阶数，如果此时给定我们的结束就是0或者1的话，那么我们直接返回0即可，如下所示：

int sz = cost.size();
if(sz == 0 || sz == 1) return 0;

之后我们就需要创建一个一维的dp表了，此时因为我们返回的是第sz位上的数据，所以此时的dp表要多创建一个空间。并且给特定位置进行填入数据的操作。

vector<int> dp(sz + 1);
dp[0] = 0;
dp[1] = 0;

在做完前面的操作以后，我们就可以通过循环的方式进行填表操作了，此时我们从2开始填入数据，直到sz，循环里面自然就是我们之前写过的状态转移方程，做完这些操作以后，我们就可以返回dp[sz]了，此题目就结束了。

for(int i = 2 ; i <= sz ; i++)
    {
        dp[i] = min(dp[i-1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
    }
return dp[sz];

2.5.代码展示

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

3.总结

本文到这里也就结束了，希望各位读者朋友好好掌握这两道题目的解题方法，之后的动态规划题目可能都会有这两道题目的影子，动态规划题目难度就是这样，如果我们找到了恰当的方法，那么遇到它们也不会犯愁了，一起写题目的时光总是短暂的，那么各位大佬们，我们下一篇文章见啦！