leetcode-70. 爬楼梯

JAVA解法

class Solution {
    public int climbStairs(int n) {
        // 少于2个台阶则台阶数与方法一样
        if(n <= 2){
            return n;
        }
        int dp1 = 1, dp2 = 2, dp = 0;
        // dp[n] = dp[n-1] + dp[n-2]
        for(int i = 3;i <= n;i++){
            dp = dp1 + dp2;
            dp1 = dp2;
            dp2 = dp;
        }
        return dp2;
    }
}

leetcode原题： 70. 爬楼梯

解法分析

到第一个台阶只有一个方法，到第二个台阶有两个方法，分别是 1+1 或 2，因此直接返回 n 即可。

大于三个台阶，可以用 dp[n] = dp[n-1] + dp[n-2] 这个公式，就是要到第 n 阶台阶需要算到第 n-1 和到 n-2 台阶的方法数之和，两者相加即为到第 n 阶台阶所有的方法，用的是递归方法。

想想解这道数学题的时候还是初三，懵懵懂懂，现已大三，六七年前了吧，那些人还好吗？