划分数的问题

dp入门：划分数

P1025 数的划分

题目链接

题意

将整数n划分成k份，每一份不能为空，任意两个方案不相同（忽略顺序），求分法总数。

思路&解法

• 十分经典的dp题目，可以这么考虑这道题：现在有k个盘子和n个苹果，要求你把苹果放到盘子里，且任何一个盘子不能为空，问有多少种不同的放法？
  这么一想就好理解多了，下面开始dp：

1. 定义状态：$dp[i][j]$：把$j$个苹果放入$i$个盘子的不同放法总数；

2. 状态转移：这么想，任何一个时候无非两种状态：

   1. $i>j$，这个时候一定会出现空盘子，所以直接$dp[i][j]=0$就行了；

   2. $i\leq j$，这个时候又出来两种情况：如果至少有一个盘子里只有一个苹果，那么这个时候的状态数就等于$dp[i-1][j-1]$；如果所有盘子都是有两个或者以上的苹果的时候，我可以先从每个盘子里取出一个苹果（共取出$i$个苹果），剩下的状态不就是$dp[i][j-i]$吗？这两种情况加起来，就是这个时候的状态。所以得出如下状态转移方程：

      $$dp[i][j]=\begin{cases}0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (i>j)\\ dp[i-1][j-1]+dp[i][j-i]\ \ \ \ \ \ (else)\end{cases}$$

AC代码

#include<bits/stdc++.h>
using namespace std;

int dp[10][205];
int n,k;
int main(){
	cin>>n>>k;
	dp[0][0] = 1;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=n;j++){
			if(i>j){
				dp[i][j] = 0;
			}else{
				dp[i][j] = dp[i-1][j-1] + dp[i][j-i];
			}
		}
	}
	cout<<dp[k][n]<<endl;
	return 0;
}

变式

• 可以看出，这一题的要求是每个划分不能为空，那么如果是可以为空呢？

  题目变为：将整数n划分成k份，每一份可以为空，任意两个方案不相同（忽略顺序），求分法总数。

思路

其实很像，只是有略微的改动。dp数组还是那么定义，状态转移如下：

1. $i>j$，此时不能是0了，因为可以为空，所以状态等于前一个状态，即$dp[i][j]=dp[i-1][j]$；

2. $i\leq j$，此时，也是两种情况：

   1. 有空盘子，其实就对应于$i>j$的情况，因为就算我苹果多，我也可以都堆在一起放对吧，所以这个状态要考虑在内；

   2. 没空盘子，那么跟上一题一样，我可以先从每个盘子里都取走一个苹果，剩下就都和上一题一样了。得出状态转移方程如下：

      $$dp[i][j]=\begin{cases}dp[i-1][j]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (i>j)\\ dp[i-1][j]+dp[i][j-i]\ \ \ \ \ \ (else)\end{cases}$$

---

代码我就不敲了 懒