动态规划------走楼梯问题

发表于 | 分类于 | | 阅读次数:

题目：

假设有10阶楼梯，每次可以跨1阶或者2阶，请问走完10阶楼梯总共有多少种走法？

动态规划解法：

设定一个名为walk（num）的函数，其返回值为走n阶楼梯的走法，则问题为walk（10）

设想一下，我们走到最后一步的时候，只有两种可能的走法：

  1. 走一步，正好走完10阶楼梯，前面走路9阶楼梯
  2. 走两步，正好走完10阶楼梯，前面走了8阶楼梯
    所以，走10阶楼梯的问题可以简化为，走9阶楼梯的走法，然后跨一步，走完。或者走8阶楼梯的走法，然后跨两步走完。
    即walk（10）=walk（9）+walk（8）

那么走9阶楼梯总共有多少种走法呢？

分析过程一样，假设已经走到最后一步，只能有两种可能的走法：

  1. 走一步，正好走完9阶楼梯，前面走了8阶楼梯
  2. 走两步，正好走完9阶楼梯，前面走了7阶楼梯
    即walk（9）=walk（8）+ walk（7）
    ……

到最后：
如果要走1阶楼梯，则只有一种走法：跨一步，即walk（1）=1
如果要走2阶楼梯，则有两种走法：一步一阶或者一阶两阶，即walk（2）=2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package com.markey.test;

public class TakeStairs {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        for(int i=1; i<11; i++){
            System.out.println("步数为"+i+":"+JumpFloorII(i));
        }
    }
    public static int walk(int stair){
        int num = 0;
        if(stair > 0){
            switch (stair) {
                case 1:
                    num = 1;
                    break;
                case 2:
                    num = 2;
                    break;
                default:
                    num = walk(stair-1)+walk(stair-2);
            }
        }
        return num;
    }
    public static int JumpFloorII(int target) {
        int num = 0;
        if (target > 0) {
            if(target == 1){
                return 1;
            }else {
                for (int i = target-1; i >= 0; i--) {
                    num += JumpFloorII(i);
                }
                num++;
            }
        }
        return num;
        
    }
}

运行效果如下：

运行结果