數(shù) n 的劃分是將 n 表示成多個(gè)正整數(shù)之和的形式
劃分可以分為兩種情況:
A 劃分的多個(gè)正整數(shù)中,正整數(shù)的數(shù)量是任意的
這又可以分為劃分的正整數(shù)中,正整數(shù)可以相同與不同兩類(lèi)
1. 劃分的多個(gè)正整數(shù)可以相同, 遞推方程可以表示為:
(1) dp[n][m]= dp[n][m-1]+ dp[n-m][m]
dp[n][m]表示整數(shù) n 的劃分中,每個(gè)數(shù)不大于 m 的劃分?jǐn)?shù)。
則劃分?jǐn)?shù)可以分為兩種情況:
a. 劃分中每個(gè)數(shù)都小于 m, 相當(dāng)于每個(gè)數(shù)不大于 m- 1, 故
劃分?jǐn)?shù)為 dp[n][m-1].
b. 劃分中有一個(gè)數(shù)為 m. 那就在 n中減去 m , 剩下的就相當(dāng)
于把 n-m 進(jìn)行劃分, 故劃分?jǐn)?shù)為 dp[n-m][m];
(2) dp[n][m]= dp[n][m+1]+ dp[n-m][m]
dp[n][m]表示整數(shù) n 的劃分中,每個(gè)數(shù)不小于 m 的劃分?jǐn)?shù)。
同理可證明該式。
2. 劃分的多個(gè)正整數(shù)互不相同,遞推方程可以表示為:
(1) dp[n][m]= dp[n][m-1]+ dp[n-m][m-1]
dp[n][m]表示整數(shù) n 的劃分中,每個(gè)數(shù)不大于 m 的劃分?jǐn)?shù)。
同樣劃分情況分為兩種情況:
a. 劃分中每個(gè)數(shù)都小于 m, 相當(dāng)于每個(gè)數(shù)不大于 m- 1,
劃分?jǐn)?shù)為 dp[n][m-1].
b. 劃分中有一個(gè)數(shù)為 m. 在 n 中減去 m, 剩下相當(dāng)對(duì)
n- m 進(jìn)行劃分,并且每一個(gè)數(shù)不大于 m- 1,故劃分?jǐn)?shù)
為 dp[n-m][m-1]
(2) dp[n][m]= dp[n][m+1]+ dp[n-m][m]
dp[n][m]表示整數(shù) n 的劃分中,每個(gè)數(shù)不小于 m 的劃分?jǐn)?shù)。
B 劃分的多個(gè)正整數(shù)中,正整數(shù)的數(shù)量是固定的
把一個(gè)整數(shù) n 無(wú)序劃分成 k 份互不相同的正整數(shù)之和的方法總數(shù)。
方程為:
dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];
證明方法參考: http://www.mydrs.org/program/html/0369.htm
另一種理解,總方法可以分為兩類(lèi):
第一類(lèi): n 份中不包含 1 的分法,為保證每份都 >= 2,可以先拿出 k 個(gè) 1 分
到每一份,然后再把剩下的 n- k 分成 k 份即可,分法有: dp[n-k][k]
第二類(lèi): n 份中至少有一份為 1 的分法,可以先那出一個(gè) 1 作為單獨(dú)的1份,剩
下的 n- 1 再分成 k- 1 份即可,分法有:dp[n-1][k-1]
相關(guān)習(xí)題:
http://acm.hit.edu.cn/ojs/show.php?Proid=1402&Contestid=0
http://acm.hnu.cn:8080/online/?action=problem&type=show&id=11299&courseid=0
posted on 2009-04-08 11:54
Darren 閱讀(2502)
評(píng)論(1) 編輯 收藏 引用