放苹果 · 背包问题

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

public class Main{
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int a = sc.nextInt(); // a 是苹果
            int b = sc.nextInt(); // b 是盘子
            // 方法一： 动态规划
            int[][] dp = new int[a + 1][b + 1];
            for(int i = 0; i <= a; ++i){
                for(int j = 1; j <= b; ++j){
                    if(i == 0 || j == 1){
                        dp[i][j] = 1;
                    }else if(j > i){
                        dp[i][j] = dp[i][i];
                    }else{
                        dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                    }
                }
            }
            System.out.println(dp[a][b]);
            // 方法二 ：递归
            // System.out.println(count(a, b));
        }
    }

    /**
     * m 苹果数
     * n 盘子数
     */
     public static int count(int m, int n){
        // 一个盘 或者 没有苹果 代表一种方案
         if(n == 1 ||m == 0 ) return 1;
         // 盘子过多情况，多余的盘子不起任何作用，最大的有效盘子是 m 个
         else if(n > m) return count(m, m);
         // 情况一： 只用 b - 1个盘子
         // 情况二： 每个盘子里先放一个苹果，等价于 a - b个苹果放到 b 个盘子
         else return count(m, n - 1) + count(m - n, n);
     }
}