两种方法:
- 斐波那契数列(找规律——爬1层1种,2层2种,3层3种,4层5种...)
- 动态规划
有必要总结一下找规律的解法:这种解法需要细心和耐心,我们一般取出前3种情况看一下规律,如果规律不明显,可以增加情况,直到过于复杂才放弃此解法。PS:前几种情况同样可以用来检验算法的正确性
动态规划——设dp[i]表示第i层的跳法,状态公式如下:
- 如果i>1,
dp[i] = dp[i-2] + dp[i-1])
- 基准1:
dp[0]=0
- 基准2:
dp[1]=1
- 基准3:
dp[2]=2
状态公式的解释:
- 最后一步跨越一个或两个台阶,因此
dp[i] = dp[i-2] + dp[i-1])
- 0个阶梯步数为0
- 1个阶梯步数为1
- 2个阶梯步数为2
为什么会有这么多基准条件呢?因为动态规划的本质是数学归纳法,而数学归纳法对于基准条件是没有限制的,因此基准条件具体应该设置多少个需要我们列举出最前面几种情况,再做一个综合判断
动态规划解法代码如下:
// // Created by jt on 2020/8/30. // #include <vector> using namespace std; class Solution { public: /** * * @param n int整型 * @return int整型 */ int climbStairs(int n) { // write code here vector<int> dp(n+1, 0); dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; ++i) { dp[i] = dp[i-2] + dp[i-1]; } return dp[n]; } };
斐波那契数列解法代码如下:
// // Created by jt on 2020/8/30. // class Solution { public: /** * * @param n int整型 * @return int整型 */ int climbStairs(int n) { // write code here int i = 0, j = 1; while(n--) { int k = i + j; i = j; j = k; } return j; } };