动态规划——走阶梯问题

 1 import java.util.Scanner;
 2 
 3 public class Main {
 4     public static void main(String args[]) {
 5         Scanner in = new Scanner(System.in);
 6         int n = in.nextInt();
 7         int m;
 8         while(n>0) {
 9             m = in.nextInt();
10             
11             switch(m) {
12             case 1:
13                 System.out.println(0);
14                 break;
15             case 2:
16                 System.out.println(1);
17                 break;
18             case 3:
19                 System.out.println(2);
20                 break;
21             default:
22                 int[] dp = new int[m+1];
23                 dp[1] = 0;
24                 dp[2] = 1;
25                 dp[3] = 2;
26                 for(int i=4;i<=m;i++) {
27                     dp[i] = dp[i-1]+dp[i-2]+1;
28                 }
29                 System.out.println(dp[m]);
30             }
31             n--;
32         }
33         in.close();
34     }
35 }