牛客 - 题（dp练习）
发布时间
阅读量：
阅读量
设给定的正整数为int n（其中n≤1×1e5），我们需要计算从初始值为零开始逐步累加若干次后达到或超过n的所有可能方案的数量。在实现过程中需要注意的是，在计算最终结果时建议对1,999,997取模以防止数值溢出。
解析：
这道题本质上是对标准斐波那契数列的一种优化。相较于标准版本，在初始条件上做出了调整：相较于标准版本，默认情况下其初始条件发生了变化。
需要注意的是，在计算过程中可能会遇到取模操作的问题。不过只要细心处理即可实现。
代码如下：
初始值设定为a、b、c分别等于1、1、1。
然后依次计算后续各项。
class GoUpstairs {
public:
int countWays(int n) {
// write code here
vector<int>dp(n+1, 1);
dp[1] = 1;
dp[2] = 2;
if(n < 3)return dp[n];
for(auto i=3; i<=n;i++){
dp[i] = ((dp[i-1] + dp[i-2])%1000000007 + dp[i-3]) % 1000000007;
}
return dp[n];全部评论 (0)
还没有任何评论哟~