题解 | #走方格的方案数#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int[][] dp;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        dp = new int[m+1][n+1];
        // System.out.println(dfs(0,0,n,m));
        count(n,m);
        System.out.println(dp[m][n]);
    }
    //方法一：深度优先
//     public static int dfs(int x,int y,int n,int m){
//         if(x>m || y>n){
//             return 0;
//         }else if(x==m && y == n){
//             return 1;
//         }
//         return dfs(x+1,y,n,m) + dfs(x,y+1,n,m);
//     }
  //方法二：动态规划
    public static void count(int n, int m) {
        for (int x = 0; x <= m; x++)
            for (int y = 0; y <= n; y++) {
                if (x == 0 && y == 0) {
                    dp[x][y] = 1;
                }else if (x > 0 && y == 0) {
                    dp[x][y] = dp[x - 1][y];
                } else if (x == 0 && y > 0) {
                    dp[x][y] = dp[x][y - 1];
                } else {
                    dp[x][y] = dp[x - 1][y] + dp[x][y - 1];
                }
            }

    }
}