image.png
解题思路
基本思路是动态规划
dp数组来记录爬i+1阶楼梯所需要的方法，dp数组在动态规划时，往往记录结果
重点是确定状态转移方程
dp[i]=dp[i-1]+dp[i-2];
动态规划的状态转移方程，因为一次可以爬一个台阶或两个台阶，所以是前二者的和
代码
class Solution {
public int climbStairs(int n) {
int [] dp=new int[n];//dp数组来记录爬i+1阶楼梯所需要的方法，dp数组在动态规划时，往往记录结果
if(n==1) dp[0]=1;//特殊情况处理一下
if(n==2) dp[1]=2;
for(int i=2;i<n;i++){
dp[0]=1;
dp[1]=2;
dp[i]=dp[i-1]+dp[i-2];//动态规划的状态转移方程，因为一次可以爬一个台阶或两个台阶，所以是前二者的和
}
return dp[n-1];//返回数组的最后一个元素
}
}
网友评论