用的dp但只有50分，求调

b1adez @ 2024-02-04 15:23:47

#include <iostream>
using namespace std;

int stair(int n){
    int dp[n+1];//走到第i个楼梯的方案数
    dp[0] = 1;
    dp[1] = 1;
    for(int i=2;i<=n;i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    //8   9   10
    //
    return dp[n] ;
}

int main(){
    int n;
    cin>>n;
    cout<<stair(n);
    return 0;
} 

by XP3301_Pipi @ 2024-02-04 15:32:39

@b1adez 要写高精度

by ltz761222 @ 2024-02-04 15:35:16

思路没有问题，但设想一下，dp[5000]=dp[4999]+dp[4998]，此时的dp肯定超过了int,如果在网上搜一下，就会发现long long int也会爆炸，此时应该采用高精度加法

by b1adez @ 2024-02-04 16:29:26

@XP3301_Pipi 谢谢大佬，我马上改

by b1adez @ 2024-02-04 16:29:42

@ltz761222 谢谢大佬，这就改

by b1adez @ 2024-02-04 16:45:25

谢谢大佬，已经改完了，代码如下

#include <iostream>
#include <vector>
using namespace std;
//高精度加法
vector <int> add(vector <int>a,vector <int>b){
    if(a.size()<b.size()){
        return (b,a);
    }
    vector <int> result;
    int temp = 0;
    for(int i=0;i<a.size();i++){
        temp += a[i];
        if(i<b.size()){
            temp += b[i];
        }
        result.push_back(temp%10);
        temp /= 10;
    }
    if(temp>0){
        result.push_back(temp);
    }
    return result;
} 

vector<int> stair(int n){
    vector<vector <int> > dp(n+1);
    dp[0].push_back(1);
    dp[1].push_back(1);
    for(int i=2;i<=n;i++){
        dp[i] = add(dp[i-1],dp[i-2]);
    }
    return dp[n];
}

int main(){
    int n;
    cin>>n;
    vector <int> result = stair(n);
    for(int i=result.size()-1;i>=0;i--){
        cout<<result[i];
    }

} 

by XP3301_Pipi @ 2024-02-04 16:46:16

@b1adez 过了没有？

by b1adez @ 2024-02-04 16:50:19

@XP3301_Pipi 过了，感谢

by XP3301_Pipi @ 2024-02-04 17:05:31

@b1adez ^o^