题解 | #放苹果#

关键是 如何 寻求 大问题与 子问题之间的关系
这里就 摘抄 各位大佬的想法

大问题：m个苹果，n个 果盘，分派苹果
小问题：
1、一次分派的时候，先空出当前的果盘，不放苹果，则是苹果数量不变，果盘数 减1， dp[m][n-1];
2、一次分派的时候，每个果盘放一个苹果，剩下的m-n个苹果如何分配到 n个果盘中，子问题，dp[m-n][n]。

import java.util.*;

public class Main{
    public static void main(String[] args){
        //new Solve1().solve();
        new Solve2().solve();
    }
}

// 递归解法
class Solve1{
    public void solve(){
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            System.out.println(count(in.nextInt(),in.nextInt()));
        }
        in.close();
    }
    public static int count(int m, int n){
        if(m<0 || n< 0) {
            return 0;
        }
        if(m == 1 || n== 1){
            return 1;
        }
        return count(m,n-1) + count(m-n,n);
    }
}

// 常规的动态规划解法
class Solve2{
    public void solve(){
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int m = in.nextInt(); // 苹果数量
            int n = in.nextInt(); // 果盘数量

            // 初始化
            int[][] dp = new int[m+1][n+1];
            for(int i = 0; i<= m; i++){
                dp[i][1] = 1;
                dp[i][0] = 0;
            }
            for(int i = 0; i < n+1; i++){
                dp[0][i] = 1;
                dp[1][i] = 1;
            }

            for(int i = 2; i <= m; i++){
                for(int j = 2; j <= n; j++){
                    if(i<j){ // 当 苹果数  小于 盘子数的时候
                        dp[i][j] = dp[i][j-1];
                    }else{ 
                        dp[i][j] = dp[i][j-1] + dp[i-j][j];
                    }
                }
            }
            System.out.println(dp[m][n]);
        }
    }
}