05. 动态规划-楼梯问题

有一座高度是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级后到达顶端；
• 我们站在第8级上，一步2级后到达顶端；

所以，最后一步可以走1级或者2级。
假设到第10级上需要F(10)步，由上述推断会发现F(10) = F(9)+F(8)

继续推导,当我们需要一步走到第9级上，可能的情况

• 我们站在第8级上，一步1级后到第9级；
• 我们站在第7级上，一步2级后到第9级；
  由上述推断会发现F(9) = F(8)+F(7)

以此类推：F(8) = F(7)+F(6)
最终得到递归公式
F(n) = F(n-1)+F(n-2)
...
F(2)=F(1)+1 即 F(2) = 2
F(1)=1

编程实现

public class Test05 {   
    public static int climb(int n) {
        if(n <= 0) {
            return 0;
        }else if(n == 1 || n == 2) {
            return n;
        }else {
            return climb(n-1)+climb(n-2);
        }
    }
    public static void main(String[] args) {
        int x = climb(10);
        System.out.println(x);
    }
}

这种方式的时间复杂度为O(2ⁿ)

2. 备忘录算法

将求解过程以二叉树的形式体现出来

以二叉树形式展示F(n)的求解过程

可以发现在计算过程中某些节点重复计算了多次（比如F(n-4)），我们是否可以通过记录某个节点第一次的运算结果，下一次再遇到计算该节点时，可以直接使用记录的数据，减少递归过程中某个节点反复多次计算。这是一种利用空间来换取时间的办法
用递归求解方式计算40级楼梯时，我的计算机运行时间大概为375ms。
使用备忘录算法后，计算40级楼梯时，我的计算机运行时间显示为0ms。
利用一个map集合存储计算过的值，其中key是n，value是F(n)

public class Test05 {   
    public static Map<Integer, Integer> map = new HashMap<Integer, Integer>();  

    public static int climb(int n) {
        if(n <= 0) {
            return 0;
        }else if(n == 1 || n == 2) {
            return n;
        }else {
            if(map.containsKey(n)) {
                return map.get(n);
            }else {
                int c = climb(n-1)+climb(n-2);
                map.put(n, c);
                return c;
            }
        }
    }
    public static void main(String[] args) {
        long l1 = System.currentTimeMillis();
        int x = climb(10);
        long l2 = System.currentTimeMillis();
        System.out.println(x);
        System.out.println("程序运行："+(l2-l1)+"ms");
    }
}

这种方式的时间复杂度为O(n)，空间复杂度也为O(n)

3. 动态规划

动态规划的思路与递归正好相反，递归一般是从后向前推导，动态规划可以理解为从前向后推导（走一步看一步）。
以动态规划的思路推导楼梯问题

• 第1级：只有1中走法 f(1)=1
• 第2级：先走第1级后走1步或直接到第2级 f(2)=2
• 第3级：先走第1级然后1级1级走，先走第1级再直接到达第3级或先直达第2级再走第3级 f(3) = f(1)+f(2)
  ...

也可以通过递归反推出规律
动态规划利用两个变量记录第三个变量的值，然后计算下一级时将计算结果向前移动

public class Test05 {   
    public static Map<Integer, Integer> map = new HashMap<Integer, Integer>();  

    public static int climb(int n) {
        if(n <= 0) {
            return 0;
        }else if(n == 1 || n == 2) {
            return n;
        }else {
            int f1 = 1;
            int f2 = 2;
            int f3 = 0;
            for(int i = 3; i <= n; i++) {
                f3 = f1+f2;
                f1 = f2;
                f2 = f3;
            }
            return f3;
        }
    }
    public static void main(String[] args) {
        long l1 = System.currentTimeMillis();
        int x = climb(10);
        long l2 = System.currentTimeMillis();
        System.out.println(x);
        System.out.println("程序运行："+(l2-l1)+"ms");
    }
}

这种方式的时间复杂度为O(n)，但空间复杂度变为O(1)