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;
} 可以看见，半江瑟瑟半江红
主要是输入的时候，爆了！
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，也是直接过了
