爬楼梯

LeetCode-70

标签：分治 动态规划

var climbStairs = function(n) {
    if(n <= 2) return n // 0,1,2个台阶时, 只有n种方法
    let dp = [1, 2] // 第1和第2个台阶
    for(let i = 2; i < n; i++) { // 从第3个台阶开始
        dp[i] = dp[i-1] + dp[i-2] // 当前台阶等于前两个台阶的和
    }
    return dp[n-1] // 第n个台阶
}