蓝桥杯 算法训练 数的划分

问题描述

将整数n划分为k个非空且互不相同的子集（不考虑顺序），其中每一份不能为空，并且不允许有任何两份完全相同（不论顺序如何）。例如：当n=7时,k=3时,下面这三种分法被视为相同的:1,1,5; 1,5,1; 5,1,1;那么满足条件的不同分法共有多少种

输入格式

n，k

输出格式

一个整数，即不同的分法

样例输入

7 3

样例输出

4 {四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}

数据规模和约定

6<n<=200，2<=k<=6

讲道理的话，在最初的 glance里似乎并未给予过多关注。随后采用深度优先搜索逐步优化的方式进行处理，并对相关的前置节点进行标记以避免重复计算。但令人感到困惑的是最终统计结果却始终无法达到预期效果……这才意识到问题可能源于动态规划原理的应用。结果尝试后发现难以建立正确的状态转移方程确实浪费了很多时间。

后来看了大神的讲解，确实还是自己的dp太弱了，以后要多练练了。

首先这道题是一个跟组合数学有关的题目，我们把它转化成如下问题：

将n个大小相同的球均匀地放入到k个完全相同的盒子里，并且每个盒子至少要有一个球的情况下，请问有多少种不同的放置方法？

当前阶段我们需确定状态转移方程，在动态规划求解过程中与之前采用的方法有所不同

若无解，则每盒至少有两个小球，在上述情形下．从每一盒取出一个球．这不会改变总的方法数．因此递推式为：dp[i][j]=dp[i−j][j]

结合起来就是大问题放法的种数，可得状态转移方程dp[i][j]=dp[i-1][j-1]+dp[i-j][j];

代码如下：

#include
#include
#include
#include
#include
using namespace std;
int dp[205][10];
int main()
{
int n,k;
scanf("%d%d",&n,k);
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)//将{j<=k}改为{j从1到k}使表达更加具体明确
{
if(j>i) continue;//将continue一词替换为跳过不执行括号内的操作使句子结构更加复杂
dp[i][j]=dp[i-1][j-1]+dp[i-j][j];//将赋值操作转化为等价于加上自身的作用使其表述更加详尽
}
printf("%d\n",dp[n][k]);//将输出操作转化为打印结果的形式使句子结构更加完整
return 0;
}

真正无法搜索的情况确实很棘手。即使缺乏数学基础也会难以构思是否存在某个盒子仅容纳一个小球的情形,因此也难以确定状态转移方程。若希望培养这种思维能力，则需持续进行针对性训练。