题解 | 放苹果

这题属于整数划分，就是将m划分成最多n个数，问有多少种分法，我们选择使用动态规划去做

dp[i][j]表示i个盘，j个苹果

先初始化，如果苹果数量为0，那么就一定是只有一种，全空的情况

然后进行递推，当苹果数量大于盘子的数量时，有两种，一种是所有盘子都用上，那么就是dp[i][j-i]，因为这种情况每个盘子至少需要一个，就等价于苹果数减去盘子数后的分法数量

还有一种情况就是苹果数量少于盘子数量，那么多余的盘子就是摆设，没用，我们选择把多余的盘子去掉改为dp[j][j]

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int m=sc.nextInt();
		int n=sc.nextInt();
		int dp[][]=new int[n+1][m+1];
//		初始化，如果只有零个苹果，那么就为1种
		for(int i=0;i<=n;i++) {
			dp[i][0]=1;
		}
		for(int i=1;i<=n;i++) {
			for(int j=0;j<=m;j++) {
				if(j>=i) {
					dp[i][j]=dp[i-1][j]+dp[i][j-i];
				}else {
					dp[i][j]=dp[j][j];
				}
				
			}
		}
		System.out.println(dp[n][m]);
		

	}

}