题解 | #放苹果#

DP：M个物品划分成N份

关键：比较盘子和苹果的个数大小

dp[i][j]：i个苹果分给j个盘子

• ①盘子比苹果多：一定有盘子是空的，摔掉多余空盘子即可： dp[i][j]=dp[i][i]
• ②盘子不比苹果多:
• 要么每个盘子都非空，相当于先给每个盘子放一个苹果，只用考虑剩下的i-j个苹果：dp[i-j][j]
• 要么至少有一个盘子空的：dp[i][j-1]

#include <iostream>
using namespace std;

const int maxn=12;
int dp[maxn][maxn];//

int main(){
  int m,n;
  while(scanf("%d%d",&m,&n)!=EOF){

    for(int i=1;i<=m;i++)dp[i][0]=0;//0个盘子，非0苹果
    for(int j=0;j<=n;j++)dp[0][j]=1;//0个苹果
    
    for(int i=1;i<=m;i++){
      for(int j=1;j<=n;j++){
        if(j>i)dp[i][j]=dp[i][i];//摔碎多余的盘子
        else dp[i][j]=dp[i-j][j]+dp[i][j-1];//没有多余的盘子+至少多余一个盘子
      }
    }
    
    printf("%d\n",dp[m][n]);
  }

  return 0;
}