70. 爬楼梯

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];//返回数组的最后一个元素
    }
}