[蓝桥杯算法从小白到大牛]动态规划第二讲:三步问题
目录
1->题目链接
2->题目解析
3->讲解算法原理
核心流程:
3.1->状态表示
3.2->状态转移方程(最重要的一步)
3.3->初始化
3.4->填表顺序
3.5->返回值
4->编写代码实现
5->您的专属鼓励师
1->题目链接
三步问题
2->题目解析
题目意思就是一次选择可以走1 或 2 或 3个台阶,现在一共有n个台阶,问我们到达第
个台阶共有多少种走法,看下我画的图你就很容易理解了.
3->讲解算法原理
核心流程:
创建一个dp表,按照题目要求去填表,最后根据题目要求返回经过处理的值
3.1->状态表示
状态表示的含义(你就直接背下来):dp[i]也就是dp表里边的值表示什么意思,状态表示就是什么
根据题目意思我们画出如下dp表,dp[i]的值表示当有i个台阶时,共有多少种方法,那我们只需要把dp表填写完成返回即可!
3.2->状态转移方程(最重要的一步)
状态转移方程的含义(直接背下来):就是dp[i] = 什么
我们画图分析,以i位置状态最近的一步进行分情况讨论:
dp[i] 表⽰⼩孩上第 i 阶楼梯的所有⽅式，那么它应该等于所有上⼀步的⽅式之和：
i. 上⼀步上⼀级台阶， dp[i] += dp[i - 1] ；
ii. 上⼀步上两级台阶， dp[i] += dp[i - 2] ；
iii. 上⼀步上三级台阶， dp[i] += dp[i - 3] ；
综上所述， dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
需要注意的是，这道题⽬说，由于结果可能很⼤，需要对结果取模
在计算的时候，三个值全部加起来再取模，即(dp[i - 1] + dp[i - 2] + dp[i - 3])%MOD是不可取的,同学们试验一下,n取题目范围最大值时网站报错 signed integer overflow
对于这类需要取模的问题，我们每计算⼀次（两个数相加/乘等），都需要取⼀次模。否则，万⼀发⽣了溢出，我们的答案就错了
3.3->初始化
通过上边递推公式我们可以看到要求dp[i]的值就需要前三个值,我们初始化的目的就是防止越界,可以看出 dp[i],在i = 0, i = 1, i = 2 的时候是没办法进行推导的,因为dp[-1],dp[-2],dp[-3]越界不是有效数据
所以我们要在填dp表之前把 i = 1, i= 2, i =3位置初始化
根据题意dp[1] = 1,dp[2] = 2, dp[3] = 4 ;
3.4->填表顺序
根据递推公式 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 毫无疑问从左到右
3.5->返回值
要求有n个台阶有多少方法,对应dp表dp[i]的值,返回dp[i]
4->编写代码实现
class Solution {
public:
const int MOD = 1e9 + 7;//防止溢出
int waysToStep(int n) {
//创建dp表
//初始化dp表
//填表
//返回
//特殊处理
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 4;
vector<int> dp(n+1,0);
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];
}
};
5->您的专属鼓励师
有些事情，你永远都没有办法做到“顶尖”，因为智力跟不上.但是所有的事情，你都可以做到“高段”，因为它需要的是时间的累积和精力的打磨.不聪明与聪明之间的区别，是很微妙的.有时候我们只会通过一次两次的结果，来判断整个人、整件事，其实这是不明智的.从小，邻居和亲戚在谈论我的时候，都会觉得我很聪明。但是只有我自己知道，我从来没有聪明过，只是看上去比较聪明而已.
修行之路确实枯燥,但是我们把问题搞懂以后就发现他是那样的美妙!一遍学不会没关系吖,多看几遍,我也是学了好多遍呢,小伙伴们肯定学的又快又好!!!最后希望写的内容对小伙伴们有所帮助,我写的如果有哪里不对的地方请在评论区或者私信指出来哦!让我们一起进步吖,任何疑问包括心情不好都可以找我聊聊,我很乐意当你的倾听者吖.
