「台阶」动态规划--台阶问题

台阶

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

如果每次走1级，需要走10步，结果可以表示成（1,1,1,1,1,1,1,1,1,1）；

如果每次走2级，需要走5步，结果可以表示成（2,2,2,2,2,）；

思考一下，你还能写出几种……

那么，共有多少种走法呢？

我们可以这样想，假设我们现在还有最后一步要走，可能的情况有哪些？

1.我们站在第9级上，一步1级后到达顶端；

2.我们站在第8级上，一步2级后到达顶端；

所以，最后一步可以走1级或者2级，不外乎两种情况。

再假设，已知从0级到9级的走法有M种，从0级到8级的走法有N种，那么思考一下，从0到10级的走法和M、N有什么关系呢？从0到10级的走法一共是多少种呢？答案是M+N。

也就是说，用F(n)来表示从0级到n级的走法，可得出

F(9)=M；

F(8)=N；

F(10)=M+N；

F(10)=F(9)+F(8);

如果已知从0到9级的走法和从0到8级的走法，问题就有答案了，那从0级到9级的走法有多少种呢？

我们依然这样想，还有一步就到9级，可能的情况有两种，从8到9和从7到9，已知了从0级到8级的走法有N种，如果再知道从0到7的走法有P种，那么从0到9级的走法就是N+P，那么可得出

F(8)=N；

F(7)=P；

F(9)=N+P；

F(9)=F(8)+F(7);

把一个复杂的问题，逐步简化成简单的问题，我们继续推断，当只剩下2级台阶和1级台阶时的走法分别是2和1。不难归纳出：

F(1)=1;

F(2)=2;

F(n)=F(n-1)+F(n-2);(n>=3)

这是一个递归，有了公式和递归结束条件，就可以写出程序了。

方法一：递归

public int getResultByRecursion(int n){
        if (n <1) {
            return 0;
        }
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        return getResultByRecursion(n-1) + getResultByRecursion(n-2);
    }

当n=30时的结果：

时间复杂度为2的n次方。

没错，这是一棵二叉树，如图所示，这里同样颜色的表示重复计算的节点，而且多数都不止重复计算了一次。我们可以对此进行优化，使用哈希表存储已经计算的节点，不再重复计算。

方法二：备忘录算法

public int getResultByMap(int n, Map<integer,Integer> map){
        if (n <1) {
            return 0;
        }
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        if(map.containsKey(n)){
            return map.get(n);
        }else{
            int value = getResultByMap(n-1,map) + getResultByMap(n-2,map);
            map.put(n,value);
            return value;
        }
    }

当n=30时的结果：

时间复杂度和空间复杂度都为O(n)。其实，我们无非使用了空间换时间，但这里很多节点不用保存，比如说，我们自底向上地来考虑这个问题，n为1和2时是显而易见的，当n=3时，可通过1和2的结果来得出，当n=4时，可通过2和3的结果来得出，我们只需要保存最近的两个结果就可以了。所以，还可以进一步优化。

方法三：动态规划

public int getResultByDP(int n){
        if (n <1) {
            return 0;
        }
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }

        int a = 1;
        int b = 2;
        int temp = 0;

        for (int i = 3; i < n+1 ; i++) {
            temp = a + b;
            a = b;
            b= temp;
        }
        return temp;
    }

时间复杂度为O(n)，空间复杂度为O(l)。

总结：动态规划是一种解决复杂问题的方法，它将大问题分成小问题或者说子问题，这些子问题是独立的，且会有重叠，也就是各子问题包含公共的子子问题，动态规划不会重复地求解公共子问题，而是对每个子问题只求解一次，将结果保存起来，从而避免每次遇到各个子问题时重新计算结果。适合采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。

如果问题的一个最优解中包含了子问题的最优解，那么该问题具有最优子结构。在上面的问题中，F(10)=F(9)+F(8)，所以F(9)和F(8)是F(10)的最优子结构。用来求解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题，对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。

动态规划--台阶问题

台阶

相关阅读

栏目导航

推荐阅读

热门阅读