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

递归-来路倒推

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            Main am = new Main();
            int count = am.count(m, n);
            System.out.println(count);
        }
        
    }

    /*
    路径规划
    每个当前点位的上一步都面临着两种选择，先向下过来的还是先向右过来的
     */
    public int count(int m, int n){
        if (m == 0 && n == 0){
            return 1;
        }else if (m > 0 && n == 0){
            return count(m - 1, n);
        }else if (n > 0 && m == 0){
            return count(m, n - 1);
        }else if (m > 0 && n > 0) {
            return count(m - 1, n) + count(m, n - 1);
        }
        return count(m - 1, n) + count(m, n - 1);
    }
}