链接: 三步问题
编写代码
class Solution {
public:
int waysToStep(int n) {
if(n == 1 || n == 2) return n;
vector<int> dp(n+1);
const int MOD = 1e9 + 7;
dp[0] = dp[1] = 1;
dp[2] = 2;
for(int i = 3;i<=n;++i)
{
dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
}
return dp[n];
}
};
文章来源：https://www.toymoban.com/news/detail-610357.html
代码优化
class Solution {
public:
int waysToStep(int n) {
if(n == 1 || n == 2) return n;
int a = 1,b = 2,c = 4,d = 0;
const int MOD = 1e9 + 7;
for(int i = 4;i<=n;++i)
{
d = ((b + c) % MOD + a) % MOD;
a = b;
b = c;
c = d;
}
return c;
}
};
文章来源地址https://www.toymoban.com/news/detail-610357.html
到了这里，关于LeetCode三步问题（动态规划）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
