题目

LeetCode.70.爬楼梯（简单）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

题解

思路

最优化问题，考虑用动态规划，看是否符合动态规划的条件。
一般从最终状态做倒推，拆解当前状态问题为上一个状态+有限的步骤。

倒推

爬到第n阶，最后一步一定是只有两种可能：

先爬到第n-1个台阶，再爬1个台阶
先爬到第n-2个台阶，再爬2个台阶

把两种可能的方法数累加就是爬到第n阶第方法数。

边界处理

爬到第1阶，只有1种爬法，即爬1个台阶。
爬到第2阶，可以从第0阶爬2个台阶，也可以从第1阶爬1个台阶，共2种爬法。

代码

class Solution {
    fun climbStairs(n: Int): Int {
        if (n == 1) return 1
        if (n == 2) return 2
        var pre1 = 2
        var pre2 = 1
        var cur = 0
        for (i in 3..n) {
            cur = pre1 + pre2
            pre2 = pre1
            pre1 = cur
        }
        return cur
    }
}