一个人的巴黎

用户名：uq_36478041918

访问量：13107

签　名：

等　　级
排　　名	103
经　　验	8031
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

数据结构-二叉排序树的基本操作【C++】
浏览：75

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C++代码）

数的划分(DFS + 回溯 +剪枝【每步详解】)(另附DP算法)

　　作者: 一个人的巴黎　　　　发表时间：2022-02-14 18:07:00 浏览：638　|　评论：2　

原题链接：信息学奥赛一本通T1440-数的划分

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int n,k;//数n，分成k份
int stack[7];//存每份分到的数
int sum=0;//计方案数
void dfs(int cnt)
{
    if(n==0) return;//n代表的是剩下的数,(当cnt==k时,n==0时,为递归出口)
    if(cnt==k){//为了分法不重，我们采用升序进行,(即最后一位数比前一位数大,就可以选择)
        if(n>=stack[cnt-1])  sum++;
        return;
    }
    for(int i=stack[cnt-1];i<=n/(k-cnt+1);i++){//对范围进行了一丢丢剪枝操作
        //从【前一个数】到【剩下的数的平均数】之间进行选择数进行划分
        //因为后一位可以和前一位相等(不下降上升)，所以我们从cnt-1开始
        //k-cnt+1代表的是我们还需要选的数的个数,n代表的是剩下的数。
        //n/(k-cnt+1)代表的是剩下要选的数的平均数
        stack[cnt]=i;//第cnt个数划分为i
        n=n-i;//剩下的数总数减i
        dfs(cnt+1);//下一个数的选择
        n=n+i;//回溯
    }
}
int main()
{
    cin>>n>>k;
    stack[0]=1;//从1开始累加或者说选数划分
    dfs(1);//从第1个开始选数，选k个
    cout<<sum<<endl;
    return 0;
}
```

动态规划算法：
设 f(n,k) 为整数 n 拆分成 k 个数字的方案数.
子问题：为整数 n-1 拆分成 k-1 个数字的方案数
那么对于每一个子问题一定可以分为以下两种情况，且不重不漏。
1.不选 1 的情况
如果不选择 1，我们把 n 拆分成 k 块的情况，可以等价于将每一块都减去1，然后分为k块，即 f(n-k,k)
2.选 1 的情况
那么就是其中一块肯定有一个 1，然后对n-1分成k-1块，即 f(n-1,k-1)。
所以总递推式为 f(n,k)=f(n-k,k)+f(n-1,k-1)
比较难想到。。。

```cpp
#include<iostream>
using namespace std;
int f[205][10];//f[n][k]代表数n划分到k个位置中且没有空的情况数
int main(){
	int n, k, i, j;
	cin>>n>>k;
	for (i = 1; i <= n; i++)
		f[i][1] = 1;//初始状态，数i划分到1个位置中只有一种情况：那个位置就是数i
 
	f[0][0] = 1;//数0划分到0个位置，也是1种情况
	for (i = 1; i <= n; i++){
		for (j = 1; j <= k && j <= i; j++){//位置数也不能大于数i，如果大于数i，那么必然后面就会出现较小的数，与不下降序列不符
			f[i][j] = f[i - 1][j - 1] + f[i - j][j];
		}
	}
	cout<<f[n][k]<<endl;
	return 0;
}
```

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

weiweiwei

好厉害，拜师了

2022-04-07 21:36:05

Glimmer

漂亮的Dp

2022-03-18 19:46:15

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.3 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

数列（C++代码）

C语言训练-计算一个整数N的阶乘（C语言代码）

数的划分(DFS + 回溯 +剪枝【每步详解】)(另附DP算法)

评论区

精彩推荐

【计算两点间的距离】（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

关于float，double变量的几点说明

1118（求助_已解决）

简单的a+b （C语言代码）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）

发工资咯（C语言代码）

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.3 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

数列 （C++代码）

C语言训练-计算一个整数N的阶乘 （C语言代码）

数的划分(DFS + 回溯 +剪枝 【每步详解】)(另附DP算法)

评论区

精彩推荐

【计算两点间的距离】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

关于float，double变量的几点说明

1118（求助_已解决）

简单的a+b （C语言代码）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）

发工资咯 （C语言代码）

数列（C++代码）

C语言训练-计算一个整数N的阶乘（C语言代码）

数的划分(DFS + 回溯 +剪枝【每步详解】)(另附DP算法)

　　评论区

【计算两点间的距离】（C语言代码）

Tom数（C语言代码）

发工资咯（C语言代码）