放苹果(动态规划)
放苹果(动态规划)
1944864971 发表于2年前
放苹果(动态规划)
  • 发表于 2年前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2679
/*
分析:
dp[i][j] 代表i个苹果 j个盘子时有多少放法

有如下几种情况
1: 苹果的个数为1时 只有一种方法
2: 盘子的个数为1时 只有一种方法
3: 当i>=j是(苹果大于盘子) 第一 :至少有一个盘子空着不放dp[i][j-1] 第二 :每个盘子放一个苹果后还剩i-j
个苹果 再计算i-j个苹果放在j个盘子的情况 dp[i-j][j];
4: 当i<j时 盘子多了就相当于i个苹果放进i个盘子的情况dp[i][i];
*/

include

int main()
{
int dp[11][11];
int t;
scanf("%d",&t);
while(t--)
{
int m,n;
scanf("%d%d",&m,&n);
for(int i=0; i<=n; i++)
dp[1][i]=dp[0][i]=1;
for(int i=0; i<=m; i++)
dp[i][0]=dp[i][1]=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]+dp[i-j][j];
else dp[i][j]=dp[i][i];
}

    printf("%d\n",dp[m][n]);

}

return 0;

}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: