數(shù) n 的劃分是將 n 表示成多個正整數(shù)之和的形式
劃分可以分為兩種情況：
A  劃分的多個正整數(shù)中，正整數(shù)的數(shù)量是任意的
   這又可以分為劃分的正整數(shù)中，正整數(shù)可以相同與不同兩類

 1.  劃分的多個正整數(shù)可以相同, 遞推方程可以表示為：
 
     (1)   dp[n][m]= dp[n][m-1]+ dp[n-m][m]
          
           dp[n][m]表示整數(shù) n 的劃分中，每個數(shù)不大于 m 的劃分?jǐn)?shù)。
           則劃分?jǐn)?shù)可以分為兩種情況:
 
           a. 劃分中每個數(shù)都小于 m， 相當(dāng)于每個數(shù)不大于 m- 1, 故
              劃分?jǐn)?shù)為 dp[n][m-1].
 
           b. 劃分中有一個數(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 的劃分中，每個數(shù)不小于 m 的劃分?jǐn)?shù)。
           同理可證明該式。
 
 2.  劃分的多個正整數(shù)互不相同，遞推方程可以表示為：
    
     (1)    dp[n][m]= dp[n][m-1]+ dp[n-m][m-1]
 
            dp[n][m]表示整數(shù) n 的劃分中，每個數(shù)不大于 m 的劃分?jǐn)?shù)。
            同樣劃分情況分為兩種情況：
 
            a.  劃分中每個數(shù)都小于 m, 相當(dāng)于每個數(shù)不大于 m- 1,
            劃分?jǐn)?shù)為 dp[n][m-1].
 
            b.  劃分中有一個數(shù)為 m. 在 n 中減去 m, 剩下相當(dāng)對
            n- m 進(jìn)行劃分，并且每一個數(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 的劃分中，每個數(shù)不小于 m 的劃分?jǐn)?shù)。

B  劃分的多個正整數(shù)中，正整數(shù)的數(shù)量是固定的
   
   把一個整數(shù) n 無序劃分成 k 份互不相同的正整數(shù)之和的方法總數(shù)。
   方程為：
  
   dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];
   證明方法參考： http://www.mydrs.org/program/html/0369.htm
   另一種理解，總方法可以分為兩類：
   第一類: n 份中不包含 1 的分法，為保證每份都 >= 2，可以先拿出 k 個 1 分
   到每一份，然后再把剩下的 n- k 分成 k 份即可，分法有: dp[n-k][k]
   第二類: n 份中至少有一份為 1 的分法，可以先那出一個 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