文章目錄

• 前言
• 一、題目
• 二、解題思路
• 結語

前言

本次訓練內容

1. 訓練DFS。
2. 訓練解題思維。

一、題目

? ? 將整數n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。

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

{1，1，5}；{1，5，1}；{5，1，1}；

問有多少種不同的分法。 輸出一個整數，即不同的分法。

輸入格式

兩個整數n，k(6<n≤200，2≤k≤6)，中間用單個空格隔開。

輸出格式

一個整數，即不同的分法。

樣例輸入

7 3

樣例輸出

4

二、解題思路

? ? ? ? 這道題目就是要我們按照對應的拆分值，拆開成對應拆分值個數，然后那個拆分出來數的和要等于原數才算成功。我先為題中的兩數建立宏定義，因為自定義函數中要使用，然后定義函數時的參數分別是1.當前處理的分割層數（從1開始）2.當前層可選擇的最小值（保證后續數不小于當前數，避免重復）3.已選數的總和；然后題中輸出為所有符合的次數，所以我就再宏定義一個計數器，原因也是自定義函數需要。創建自定函數后并設置對應的三個形參，然后我先判斷計數條件和返回調用的情況，然后接著就是遞歸回溯過程。實現代碼如下：

#include <bits/stdc++.h>
using namespace std;
#define Max 200
int sum=0;
int n,k;
int arry[Max];//存儲塊值數組
void DFS(int a,int b,int c) {//思路里對應的三個形參if (a>k) {if (c==n) {//判斷計數器增加條件sum++;}return;//返回調用}for (int i=b;i<=n-c;i++) {arry[a]=i;//把可能值存入數組DFS(a+1,i,c+i);//遞歸過程}
}
int main() {cin>>n>>k;DFS(1,1,0);cout<<sum;
}

????????for循環中的n-c是保證剩余總和足夠分配給后續層數；主函數調用DFS時，前兩項不能為0，第一個是因為保證它是第一個數，第二個是因為可填入的最小值為1。

總結

? ? ? ? 今天的題目對于DFS的遞歸回溯邏輯進行了進一步的考驗，它需要我通過對它遞歸回溯邏輯的熟悉理解來思考并解決問題。與昨天的DFS基礎相比，雖然原理是一樣的，但是相對于昨天的遞歸回溯的過程，今天的寫法讓我對其的理解和思考更加深入，也對它這個過程有更進一步的理解。由于之前學的不是很深，所以今天在理解的過程中花了許多時間來模擬過程，到最后花了一多小時才解出題目；后續需要多推理其邏輯，以便熟練掌握。