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

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        System.out.println(sum(n, m));
    }
    public static int sum(int n, int m) {
        int num = 0;
        if (m > 0 && n > 0) {
            if (m == 1) {
                if (n == 1) {
                    num = 2;
                } else {
//                    m==1&&n>1
                    num = sum(n - 1, 1) + 1;
                }

            } else {
//                m>1
                if (n == 1) {
                    num = sum(1, m - 1) + 1;;
                } else {
//                    m>1&&n>1
                    num = sum(n - 1, m) + sum(n, m - 1);
                }
            }
        }
        return num;
    }
}

类似于放苹果和青蛙跳的递归问题 主要分类标准为（m==1）{n==1 {};n>1{}}以及（m>1）{n==1{};n>1{}}