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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            // 递归
            System.out.println(rec(n, m));
            // 动态规划
            // System.out.println(dp(n, m));
            // 组合
            // System.out.println(combine(n, m));
        }
    }

    public static int rec(int n, int m) {
        if (m == 0 || n == 0) {
            return 1;
        }
        return rec(m - 1, n) + rec(m, n - 1);
    }

    public static int dp(int n, int m) {
        // n个格子就有n+1条线
        n++;
        m++;
        // 避免处理边界问题（实际上空间消耗增加了）
        int[][] d = new int[n + 1][m + 1];
        // 初始子问题：只有一个点时有一条路，其他时候都为它上面的路和加左边的路和
        d[1][1] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                d[i][j] += d[i - 1][j] + d[i][j - 1];
            }
        }
        return  d[n][m];
    }
    /**
     * 排列组合
     * 一共要走 m+n步 在其中挑选n步向下的 C(n, n+m) = (m+n)! / (n!*m!)
     */
    public static int combine(int n, int m) {
        return factorial(m + n) / (factorial(m) * factorial(n));
    }
    public static int factorial(int n) {
        int sum = 1;
        for (int i = 1; i <= n; i++) {
            sum *= i;
        }
        return sum;
    }
}