一个人的巴黎

用户名：uq_36478041918

访问量：14988

签　名：

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

　　自我简介：

TA的其他文章

优秀的拆分,方法都会，注意细节即可，考察递归思想
浏览：361

奖学金，运用sort函数对结构体类型排序
浏览：283

奖学金，运用sort函数对结构体类型排序
浏览：148

你可能喜欢

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

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

　　作者: 一个人的巴黎　　　　发表时间：2022-02-14 18:07:00 浏览：702　|　评论：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语言程序设计教程（第三版）课后习题11.8 （C语言代码）

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

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

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

字符串对比（C语言代码）

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

评论区

精彩推荐

校门外的树（C语言代码）

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

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

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

用筛法求之N内的素数。（C++代码）

水仙花（C语言代码）

字符逆序（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

理财计划（C语言代码）

C二级辅导-等差数列（C语言代码）

一个人的巴黎

TA的其他文章

你可能喜欢

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

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

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

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

字符串对比 （C语言代码）

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

评论区

精彩推荐

校门外的树 （C语言代码）

WU-蓝桥杯算法提高VIP-勾股数 （C++代码）

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

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

用筛法求之N内的素数。 （C++代码）

水仙花 （C语言代码）

字符逆序 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

理财计划 （C语言代码）

C二级辅导-等差数列 （C语言代码）

字符串对比（C语言代码）

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

　　评论区

校门外的树（C语言代码）

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

用筛法求之N内的素数。（C++代码）

水仙花（C语言代码）

字符逆序（C语言代码）

理财计划（C语言代码）

C二级辅导-等差数列（C语言代码）