动态规划-楼梯问题

1、问题描述

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

输入输出描述

Input

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

示例：

Sample Input

2

2

3

Sample Output

1

2

2、思路分析

利用 动态规划（DP，dynamic programming） 思想，简单来说：大事化小小事化了

假设10级，考虑只差最后一步到10级，一步走1阶或2阶，只有两种可能：到9阶和到8阶。

如果到9阶的走法有X种，到8阶的走法有Y种，那么，总走法=X+Y。

即：F(10)=F(9)+F(8)

同理，F(9)=F(8)+F(7)，F(8)=F(7)+F(6)，这样问题可以从10阶到 [9和8] 阶，再到 [9和8] 拆开的阶，这样往下，分阶段将问题简化。

寻找基准或者初始解：当为F(2)和F(1)时，前者有两种走法（1+1，2），后者有一种走法（1）。

即：①F(2)=2，F(1)=1。再加上②F(10)=F(9)+F(8)，

得到三个动态规划的概念：

【 最优子结构 】：F(9)和F(8)，是F(10)的最优子结构

【 边界 】：F(1)和F(2)是问题的边界，无法再简化/拆解

【 状态转移方程 】：F(10)=F(9)+F(8)，上下阶段的关系

递归公式： F(n)=F(n-1)+F(n-2) ，实为斐波那契数列的递归公式。

3、程序实现

首先用递归进行实现，与动态规划做比较。前者代码简洁，但执行效率不如后者。

1）递归

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

2）动态规划

从底到上推导：

F(1)=1，F(2)=2，

F(3)=F(2)+F(1)=1+2

F(4)=F(3)+F(2)=3+2

每次迭代，只保留之前的两个状态，即可推导新的状态。

源程序：

import java.util.Scanner;

/**
 * Input:输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。
 * Output:对于每个测试实例，请输出不同走法的数量
 */
public class DPSumsung {

    public static int getWays(int n) {
        if(n<1) return 0;
        if(n==1) return 1;
        if(n==2) return 2;
        
        int a=1;
        int b=2;
        int next=0;
        for(int i=3;i<=n;i++) {
            next=a+b;
            a=b;
            b=next;
        }
        return next;
    }
    
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
        int count=sc.nextInt();
        int[] ways=new int[count];
        int i=0;
        int n=sc.nextInt();
        while(n>=1&&n<=40) {         
            ways[i++]=DPSumsung.getWays(n);
            if(i>=count)
                break;
            n=sc.nextInt();
        }
        for(int temp:ways) {
            System.out.println(temp);
        }
        sc.close();
    }
}

4、算法分析

时间复杂度为O(N)，空间复杂度为O(1)。