Climbing Stairs

原題鏈接Climbing Stairs

找到有多少個(gè)組合的和是給定的n，要求組合中的每個(gè)數(shù)字只能是1和2

動(dòng)態(tài)規(guī)劃即可
代碼如下

class Solution { public:int climbStairs(int n) {vector<int> dp(n + 1);dp[0] = dp[1] = 1;/* 當(dāng)前的位置只能由前一個(gè)位置移動(dòng)一步，或者前前位置移動(dòng)兩步到達(dá) *//* dp[i]表示從開始達(dá)到i位置有多少種可能 */for(int i = 2; i <= n; ++i)dp[i] = dp[i - 1] + dp[i - 2];return dp[n];} };

像這種每個(gè)當(dāng)前狀態(tài)由以前的狀態(tài)決定（或者說當(dāng)前狀態(tài)決定之后的狀態(tài)）的問題都可以用動(dòng)態(tài)規(guī)劃解決，不過需要分析動(dòng)態(tài)規(guī)劃數(shù)組應(yīng)該表示什么。

總結(jié)

以上是生活随笔為你收集整理的每天一道LeetCode-----找到有多少个组合加起来和是n，每个组合的数字只能是1或者2的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。