题解 | #放苹果#

import java.util.; import java.io.;

public class Main{ public static void main(String[] args) {

    final InputStreamReader reader = new InputStreamReader(System.in);

    try (final BufferedReader br = new BufferedReader(reader)) {

        final String[] split = br.readLine().split(" ");
        int m=Integer.parseInt(split[0]);
        int n=Integer.parseInt(split[1]);

        System.out.println(count(m,n));


    }catch (IOException e ){
        System.out.println(e.getMessage());
    }
}
public static int count (int m,int n ){
    /*
    * dp[m-n][n] : 每个盘至少有一个苹果
    * dp[m][n-1] : 至少有一个盘没有苹果
    * dp[m][n] : 当前状态下排列情况
    *
    * 状态转移方程
    *   苹果大于盘子: dp[m][n] = dp[m-n][n] + dp[m][n-1];
    *   苹果小于盘子: dp[m][n] =dp[m][n-1]
    * */




    int[][] dp = new int[m+1][n+1];
    //初始化只有一个盘子的情况
    for (int i = 0 ;i<= m;i++){
        dp[i][1]=1;
    }
    //初始化没有苹果的情况
    for (int i=0;i<=n;i++){
        dp[0][i]=1;
    }

    for (int i = 1 ;i<=m ;i++){

        for (int j = 2 ; j<=n ; j++){
            //苹果大于盘子
            if (i>=j) {
                dp[i][j] = dp[i-j][j]+dp[i][j-1];
            }else {
                dp[i][j] = dp[i][j-1]; 
            }

        }

    }
    return  dp[m][n];

}

}