題目描述

將整數?n?分成?k?份，且每份不能為空，任意兩個方案不相同（不考慮順序）。

例如：n=7，k=3，下面三種分法被認為是相同的。

1,1,5;
1,5,1;
5,1,1.

問有多少種不同的分法。

輸入格式

n,k?（6<n≤200，2≤k≤6）

輸出格式

1?個整數，即不同的分法。

輸入輸出樣例

輸入 #1復制

7 3

輸出 #1復制

4

說明/提示

四種分法為：
1,1,5;
1,2,4;
1,3,3;
2,2,3.

題目鏈接：P1025 [NOIP 2001 提高組] 數的劃分 - 洛谷
學習鏈接：DFS正確入門方式 | DFS + 遞歸與遞推習題課(下) | 一節課教你爆搜!_嗶哩嗶哩_bilibili

解題思路：

1. 保證枚舉到的當前位置的數>=下一個位置
2. 保證排列元素求和==n,每個排列有k個元素?

代碼如下：?

#include<bits/stdc++.h>
using namespace std;
int n;
int k;//劃分份數 
int cnt=0;void dfs(int start,int x,int sum)
{
//	//剪枝：如果當前排列和超過了n，直接結束搜索（該剪枝不夠強，還是會超時） 
//	if(sum>n)	return ;//如果枚舉的位置超過了k份if(x>k){//判斷該排列之和是否==nif(sum==n){cnt++;//累計方案數 } return ;//結束搜索 } //要剪枝：若剩下的幾個位置用當前起始值填充(k-x+1)*i + 當前排列枚舉元素之和sum>n的話就要剪掉，否則會超時 for(int i=start;sum+(k-x+1)*i<=n;i++){//開始枚舉下一個位置dfs(i,x+1,sum+i); }
} 
int main()
{cin>>n>>k;//枚舉第一個位置,第一個位置從1開始枚舉，因為每份不能為空，當前元素和為0 dfs(1,1,0); cout<<cnt<<endl;return 0;
} 

?希望能幫助到各位同志，祝天天開心，學業進步！