动态规划——走阶梯问题

问题：

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

注：规定从一级到一级有0种走法。

分析：

（1）公式 F(n) = F(n-1)+F(n-2)。

（2）初始化：因为F(1) = 0，所以F(2) = 1;F(3) = 2。

（3）使用switch实现多重判断

code :

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m;
        while(n>0) {
            m = in.nextInt();
            
            switch(m) {
            case 1:
                System.out.println(0);
                break;
            case 2:
                System.out.println(1);
                break;
            case 3:
                System.out.println(2);
                break;
            default:
                int[] dp = new int[m+1];
                dp[1] = 0;
                dp[2] = 1;
                dp[3] = 2;
                for(int i=4;i<=m;i++) {
                    dp[i] = dp[i-1]+dp[i-2]+1;
                }
                System.out.println(dp[m]);
            }
            n--;
        }
        in.close();
    }
}