• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            數(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)  編輯 收藏 引用

            評(píng)論:
            # re: 整數(shù)劃分問(wèn)題[未登錄](méi) 2009-04-20 19:02 | wolf
            謝謝你的總結(jié)了。。  回復(fù)  更多評(píng)論
              

            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            一级女性全黄久久生活片免费 | 亚洲午夜无码AV毛片久久| 国产精品无码久久综合| 奇米影视7777久久精品| 久久久精品2019免费观看| 青草国产精品久久久久久| 久久久久无码精品国产不卡| 蜜臀av性久久久久蜜臀aⅴ麻豆| 国产精品久久久久久五月尺| 久久久精品久久久久影院| 合区精品久久久中文字幕一区| 欧美久久天天综合香蕉伊| 久久无码AV中文出轨人妻| 久久一区二区免费播放| 久久精品国产男包| 国产精品99精品久久免费| 久久综合狠狠色综合伊人| 色噜噜狠狠先锋影音久久| 久久人人爽人人爽AV片| 国产一区二区久久久| 久久狠狠高潮亚洲精品| 日本三级久久网| 久久久久久久久66精品片| 久久精品国产99久久无毒不卡| 狠狠色丁香久久综合婷婷| 国产精品内射久久久久欢欢| 久久亚洲2019中文字幕| 久久亚洲私人国产精品vA| 国产视频久久| 久久久久久国产精品无码超碰| 国产精品久久久天天影视香蕉| 国产色综合久久无码有码| 99久久精品日本一区二区免费| 久久久久亚洲AV成人网人人网站| 国产成年无码久久久免费| 热久久国产精品| 无码人妻久久久一区二区三区| 国产精品无码久久综合网| 欧美噜噜久久久XXX| 久久亚洲精品无码观看不卡| 大伊人青草狠狠久久|