1304:数的划分

2024-01-02 20:58:09

【算法分析】
? ? ? ?本题可以类比信息学奥赛一本通 1222 放苹果,上题是允许有空的盘子,本题数字拆分问题可以等价地描述为:将n个相同的苹果分在k个相同的盘子中,每个盘子至少有1个苹果的方案数。下面在放苹果的问题背景下描述思路。

1. 状态定义
状态定义:dp[i][j]:将i个相同的苹果分放在j个相同的盘子中的方案数。
初始状态:将i个相同的苹果放在1个相同的盘子中,有1种方案,即dp[i][1] = 1
如果苹果数小于盘子数,那么一定有某个盘子中分不到苹果,这不符合每个盘子至少有1个苹果,因此只有0种方案。即当i < j时,dp[i][j] = 0

2. 状态转移方程
考虑分放苹果后是否存在某盘子中只有1个苹果,来分割集合。

子集1:存在某盘子中只有1个苹果,那么该情况下的方案数等同于:将i-1个苹果放入其余j-1个盘子的方案数,为:dp[i-1][j-1]
子集2:不存在某盘子中只有1个苹果,也就是每个盘子的苹果数量大于等于2。这相当于先在每个盘子各放一个苹果,用掉了j个苹果。然后要做的事情相当于:将剩下的i-j个苹果放入j个盘子,每个盘子中放至少1个苹果。该情况的方案数为:dp[i-j][j]
以上两种情况得到的方案数加和,即为将i个相同的苹果分放在j个相同的盘子中的方案数。即dp[i][j] = dp[i-1][j-1] + dp[i-j][j]
?

【参考代码】

#include<bits/stdc++.h>
using namespace std;
int n, k, dp[205][10];//dp[i][j]:将数字i拆分为j个数字相加的方案数 
int main()
{
    cin >> n >> k;
    for(int i = 0; i <= n; ++i)
    	dp[i][1] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= k && j <= i; ++j)
            dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
    cout << dp[n][k];
    return 0;
}

文章来源:https://blog.csdn.net/pheatonhb/article/details/135343931
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。