在高中的時候，我們接觸到的排列組合問題是將相同元素放到不同空間，這個很好求，
那么相同元素分配到相同空間怎么辦呢？
我在網上大概查了一下，但是也沒有解釋的很詳細的，所以就根據已有的進行了推導，并對已有的部分資料中的錯誤也在此進行了更正，
接下來我將以放雞蛋問題作為例子
設有n個雞蛋，m個籃子，問：
- 將n個雞蛋放到m個籃子里，允許有空籃子，有幾種方法？
- 將n個雞蛋放到m個籃子里，且不允許有空籃子，有幾種方法?
ps:n = 7,m = 3時，1，1，5；1，5，1；5，1，1被認為是同一種分法
設F(m,n)：將n個雞蛋給m個籃子，且籃子可以為空
設T(m,n)：將n個雞蛋給m個籃子，且籃子不可以為空
對問題2：將n個雞蛋放到m個籃子里，且不允許有空籃子，有幾種方法?
m = n:籃子數 = 雞蛋數時
很明顯，此時只能一個籃子里放一個雞蛋，所以只有一種方法，m > n:籃子數 > 雞蛋數時
不可能，m < n:籃子數 < 雞蛋數時
可以先給m個籃子里裝入一個雞蛋，此時就滿足了題意，沒有籃子是空的，
剩余的雞蛋為n-m個再分到m個籃子中，此時允許有籃子分不到雞蛋，即T(m,n) = F(m,n-m)，
此時就轉化為將n-m個雞蛋裝入m個籃子里，且允許有空籃子的問題了，
對于問題1：將n個雞蛋放到m個籃子里，允許有空籃子，有幾種方法？
方法數 = 所有籃子都不空 + 空1個籃子 + 空2個籃子 + ... +空m -1個籃子
即F(m,n) = T(m,n) + T(m-1,n) + T(m-2,n) + ... + T(1,n)，根據上面對問題2的分析我們可知：T(m,n) = F(m,n-m)，則上式變為：
F(m,n) = F(m,n-m) + F(m-1,n)這也就是我們后邊要用到的遞回原型，
對于遞回來說，我們要考慮好它的終止條件：
- 當 m = 1即籃子數 = 1時，無論有多少的雞蛋都只能放進這個籃子里，所以回傳1；
- 當 n = 0即雞蛋數 = 0時，無論有多少籃子，也沒有雞蛋可以放，所以回傳0；
- 當 n < m 即雞蛋數 <籃子數時，肯定會有n - m個空籃子，所以我們令m = n；
但此時我們得到的遞回式還并不是我們最終需要的，在此我以F(2,2)作為例子：
F(2,2)指將兩個雞蛋放入兩個籃子中，且允許有空籃子，那我們仔細想一想其實就能想出來，只有兩種分配方法：1,1和2，0，
但此時若我們用上述得到的式子進行計算可得：F(2,2) = F(2,0) + F(1,2) = 1與真實答案不符，仔細觀察該式，可知原因：當 m = n時，直接利用變化來的式子未考慮一個籃子放一個雞蛋的情況，所以還要在上面得到的式子的基礎上，對終止條件進行補充：
- 當 n = m時，令
分配方法數 += 1，
以數的劃分為例題
我用c++以上述思路來解決數的劃分：
題目描述
將整數 n 分成 k 份，且每份不能為空，問有多少種不同的分法，當 n=7, k=3 時，下面三種分法被認為是相同的：1,1,5; 1,5,1; 5,1,1
輸入格式
一行兩個數 n, k，
輸出格式
一行一個整數，即不同的分法數，
輸入資料
7 3
輸出資料
4
四種分法為：1,1,5；1,2,4；1,3,3；2,2,3，
思路：在這里我把數看作雞蛋，分法看作籃子，
/**
*Filename:heli
*Author:wan
*Date:2022.1.14
*version:1.3
*Description:heli
*/
#include <bits/stdc++.h>
using namespace std;
int number;//分配方法數
int give_space(int m,int n){
//籃子是m,雞蛋是n
int sum = 0;
if(m ==n){
sum += 1;
// printf("sum:%d\n",sum);
}
if(n == 0){//蛋 = 0
return 0;
}
if(m == 1||m == 0){//籃子 = 0/1
return 1;
}
if(n < m){//雞蛋數<籃子數時，籃子 = 雞蛋
m = n;
//此處判斷很重要，否則計算時會少1
return give_space(m,n);
}
//printf("%d %d\n",m,n);
sum += give_space(m,n-m);
sum += give_space(m-1,n);
return sum;
}
int main(){
int n,k;
scanf("%d %d",&n,&k);
if(n <= k){
number = 1;
}
else{
//k = m,籃子，n是雞蛋
number += give_space(k,n - k);
}
printf("%d",number);
return 0;
}
ps:在終止條件中，當 n < m 即雞蛋數 <籃子數時，我們令m = n后記得把這個m,n重新傳進去，否則會少考慮將每個籃子里放一個雞蛋的情況，
最后的最后：本文基于個人理解，可能存在錯誤的地方，如有錯誤請各位大佬指出，我會盡快進行修改，
希望有幫到你呀:D
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412984.html
標籤：其他
上一篇：7-2 素數對猜想
下一篇：演算法競賽——最短路問題