hot100-爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

动态规划问题

到达第k个台阶，要么是从第k-1个台阶跳一次要么是从第k-2个台阶跳俩台阶，那么可得动态规划方程： d[i] = d[i-1]+d[i-2];

后对空间进行优化，发现d[i]只依赖d[i-1]与d[i-2]，所以可以只用三个变量存储而不用开辟数组，让三个变量动态滚动即可。

public static int climbStairs(int n) {
    int[] d = new int[n+1];
    d[0] = 1;
    d[1] = 1;
    if(n==1)return 1;
    for (int i = 2; i <= n; i++) {
        d[i] = d[i-1]+d[i-2];
    }
    return d[n];

}
//空间优化后
public static int climbStairs2(int n){
    int m = 1;
    int k = 1;
    int l = 0;

    for (int i = 2; i <=n; i++) {
        l = m+k;
        m = k;
        k = l;
    }
    return l;
}