Leetcode70. 階段を登る(C言語)


Leetcode70. 階段を登る(C言語)
アルゴリズム-ダイナミックプランニング(フィボナッチ):アルゴリズムとデータ構造の参照
階段を登っているとします.屋上に着くにはn階(正の整数)が必要です.毎回1つか2つの階段を登ることができます.屋上に登る方法はいくつありますか?例:入力:3出力:3
構想:ダイナミックプランニング(最適解はそのサブ問題の最適解から効率的に構築できる)
第ii段階は、第(i−1)(i−1)段階の後に1段階上に登る2つの方法によって得ることができる.(i−2)(i−2)段目の後に22段上に登る.したがって,ii次に到達する方法の総数は,(i−1)(i−1)次と(i−2)(i−2)次の方法数の和である.
dp[i]dp[i]をii段目に到達可能な方法の総数を表す:dp[i]=dp[i−1]+dp[i−2]dp[i]=dp[i−1]+dp[i−2]
leetcode公式問題解
コード:
int climbStairs(int n){
    if(n<=2)    return n;

    int pre1=1,pre2=2;		//       (         )
    for(int i=2;i<n;i++){
        int cur=pre1+pre2;
        pre1=pre2;			//pre1,pre2  
        pre2=cur;
    }
    
    return pre2;
}