动态规划 / 爬楼梯

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

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

Clarification：
这是一道动态规划的题目。回溯、贪心和动态规划并没有明显的区隔，如果回溯（递归）去掉了重复，贪心不只是关心局部最优、而是关心全局最优，那么就变成了动态规划。

动态规划，又称动态递推。它有两件最重要的事要做：首先是递推状态的确定，在斐波那契数列中，就是数列的值；在迷宫问题中，就是到达整个位置可以有的走法；在爬楼梯问题中，状态就是到达当前位置所能有的走法。

递推思想是从结果出发的，放在递归树里看，就是从叶子节点出发。递归树中每个节点都是一个状态。通常会有大量的重复计算，因此也存在引入了备忘录的递归方法。即先判断是否已经计算过，倘若已经存在，就直接返回。备忘录通常是使用一个一维或二维的布尔类型数组来表示已经计算过/没有计算过。

其次就是状态方程。递推，顾名思义，前面的状态都是通过后面的状态计算出来的。在爬楼梯问题中，由于一次可以走1级、或是2级，因此假设走n阶台阶的走法是f(n)，那么f(n) = f(n-1)+f(n-2)，也就是从第n-1阶台阶走一步，或是从第n-2阶台阶走两步。

Possible Solution：

1. 贪心
2. 动态规划
3. BP
4. 递归

Coding：

// 这是我第一次写的代码
class Solution {
    public int climbStairs(int n) {
        if(n==1){   // Initial state
            return 1;
        }else{
            return climbStairs(n-1) + climbStairs(n-2);
        }
    }
}

结果报错，错误是我从来没见过的。 image.png

哈哈，不觉得名字很好玩吗，暗合了某著名同性交友网站。

我刚才的解法，其实更像是简单粗暴的回溯或是递归方法，而且没有加备忘录。备忘录在实现中，其实就是增加一个判断条件。当然也需要消耗一点内存。

// 这是第二次写的代码，其实已经修改了多次，但还是没有通过
// Arraylist的set方法处总是报OutOfBoundry的错误
class Solution {
    public int climbStairs(int n) {
        ArrayList<Integer> result = new ArrayList<>(n);   //result数组代表的是第n阶的走法数量
        if(n==1)  return 1;
        else{
            result.set(0,1);
            result.set(1,1);
            for(int i=2; i<n; i++){
                result.set(i, result.get(i-1) + result.get(i-2)) ;
           }
           return result.get(n-1);    
        }
    }
}

上面的代码采用了“当然我是在扯淡”博客中提到的树形结构，确实会让代码看上去更有逻辑。

image.png

这是大神的代码，仔细对比下，有几个区别。

1. 他采用的是int[] mem = new int[n]，省去了装箱拆箱操作。
2. 在n=0,1,2的时候，都可以直接return n。

学习大神的代码之后，我这样写：

class Solution {
    public int climbStairs(int n) {
        if(n==0||n==1||n==2){
            return n;
        }else{
            int[] result = new int[n];   //result数组代表的是第n阶的走法数量
            result[0] = 1;
            result[1] = 2;
            for(int i=2; i<n; i++){
                result[i] = result[i-1] + result[i-2];
           }
           return result[n-1];    
        }
    }
}

需要注意的地方有：

1. 数组的下标是从0开始的，因此result[0]表示的是走一节台阶的走法。
2. 使用数组，还是直接使用方法本身。