P10250 [GESP样题六级] 下楼梯题解

2024/10/26 1:19:17 来源：https://blog.csdn.net/Tjnk_bj/article/details/142662309 浏览: 次关键词：P10250 [GESP样题六级] 下楼梯题解

~~孩子们，我回来了~~

先看题

这很明显就是动态规划啊

先打个表

不难发现，

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

敲代码，把别的补上就好了

#include<bits/stdc++.h>

#include<bits/stdc++.h>
using namespace std;int main(){unsigned long long dp[65]={0,1,2,4};for(int i=4;i<61;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];} int n;cin>>n;cout<<dp[n];return 0;
}

可以看见，半江瑟瑟半江红

主要是输入 $\geqslant 37$ 的时候，爆了！

dp[36]=2082876103;

dp[37]=3831006429;

INT_MAX=2147483647;

3831006429>2147483647,因此需要救一下，用long long

#include<bits/stdc++.h>
using namespace std;int main(){unsigned long long dp[65]={0,1,2,4};for(int i=4;i<61;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];} int n;cin>>n;cout<<dp[n];return 0;
}

OK，也是直接过了