Leetcode70. 階段を登る(C言語)
2358 ワード
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公式問題解
コード:
アルゴリズム-ダイナミックプランニング(フィボナッチ):アルゴリズムとデータ構造の参照
階段を登っているとします.屋上に着くには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;
}