70. 爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：
輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1.1 階 + 1 階
2.2 階

示例 2：
輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。
1.1 階 + 1 階 + 1 階
2.1 階 + 2 階
3.2 階 + 1 階

提示：
1 <= n <= 45

解題思路

①狀態(tài)表示：1.集合f[i]表示的是到達(dá)i階臺(tái)階時(shí)，所擁有的方案數(shù)。2.操作：求+。
②狀態(tài)計(jì)算：我們考慮i，i層臺(tái)階可以i-1層臺(tái)階和i-2層臺(tái)階得到，由于到達(dá)兩者的目的并不相同，因此這兩種方案數(shù)量相加即可
③初始狀態(tài) ：f [1]=1, f[2] =2

代碼

class Solution {
public:int climbStairs(int n) {if(n<=1) return n;vector<int> f(n+1);//開(kāi)n+1防止數(shù)組越界f[1]=1,f[2]=2;for(int i=3;i<=n;i++){f[i]=f[i-1]+f[i-2];}return f[n];}
};