题目

爬n级台阶，每次只能爬一级或两级，一共多少种方法？

思路

动态规划

爬到第n层的方法要么是从第 n-1 层一步上来的，要不就是从 n-2 层2步上来的，所以：dp[n] = dp[n-1] + dp[n-2]

class Solution { public: int climbStairs(int n) { if(n<=1){ return 1; } vector<int> dp(n); dp[0] = 1; dp[1] = 2; for(int i=2; i<n; ++i){ dp[i]=dp[i-1]+dp[i-2]; } return dp.back(); } };

不同n对应的方法总数 实质是一个斐波那契数列：1，2，3，5，8，13，……