<p> </p>
<p class="MsoNormal"><span lang="ZH-CN">整数划分部分问题和算法</span></p>
<p class="MsoNormal"> </p>
<table border="0" cellpadding="0" class="MsoNormalTable" style="width: 100%;"><tbody><tr><td width="99%"> <p class="MsoNormal"><strong><span lang="ZH-CN">一．基本划分问题</span></strong></p> <p class="MsoNormal"><strong><span lang="ZH-CN">问题描述</span></strong><span lang="ZH-CN">：给定一个正整数</span>n<span lang="ZH-CN">，求将其划分为</span>m<span lang="ZH-CN">份的不同方法数。</span></p> <p class="MsoNormal"><strong><span lang="ZH-CN">问题分析</span></strong><span lang="ZH-CN">：</span></p> <p class="MsoNormal">(1) <span lang="ZH-CN">首先，何谓不同方法总数？即两个不同的划分的元素不能完全相同，</span>eg<span lang="ZH-CN">：</span>10 = 1+2+3+4<span lang="ZH-CN">，是</span>10<span lang="ZH-CN">的一个划分，那么</span>10 = 2+1+3+4<span lang="ZH-CN">也应该是</span>10<span lang="ZH-CN">的一个划分，但是由于这两个划分的元素完全相同，所以实际只能算同一种划分。</span></p> <p class="MsoNormal">(2) <span lang="ZH-CN">搞清楚不同方法数之后，那么如果我们在划分时只要按照不下降排列的方式进行划分就不会有重复，这样进行下去就可以得到最后的方法总数</span></p> <p class="MsoNormal"><strong><span lang="ZH-CN">算法设计</span></strong><span lang="ZH-CN">：</span></p> <p class="MsoNormal">(1) <span lang="ZH-CN">首先看原始的动态规划算法设计：考虑划分过程中的最大数</span> k<span lang="ZH-CN">，令</span>f[i][j][k]<span lang="ZH-CN">表示将整数</span>j<span lang="ZH-CN">划分成</span> i <span lang="ZH-CN">份，而最后一个数最大为</span> k <span lang="ZH-CN">的划分方案总数。那么可见：该状态</span>(i, j, k)<span lang="ZH-CN">可由前面</span>“i-1”<span lang="ZH-CN">份的</span>“j-k”<span lang="ZH-CN">加上</span>“<span lang="ZH-CN">一份</span>k”<span lang="ZH-CN">而来，因此当前状态的方案总数就等于</span>“j-k”<span lang="ZH-CN">划分为</span>i-1<span lang="ZH-CN">份的所有最大加数小于等于</span>k<span lang="ZH-CN">的方案数至和。得到状态转移方程：</span>f[i][j][k] = SUM{ f[i-1][j-k][l] | 0 <= l <= k }</p> <p class="MsoNormal"> DP<span lang="ZH-CN">算法</span>1<span lang="ZH-CN">：</span> O(n^3*m)</p> <p class="MsoNormal"> Set all f[i][j][k] = 0;</p> <p class="MsoNormal"> f[0][0][0] = 1;</p> <p class="MsoNormal"> for(i = 1; i <= m; i++)</p> <p class="MsoNormal"> for(j = i; j <= n; j++)</p> <p class="MsoNormal"> for(k = 1; k <= j; k++)</p> <p class="MsoNormal"> for(l = 0; l <= k; l++)</p> <p class="MsoNormal"> f[i][j][k] += f[i-1][j-k][l];</p> <p class="MsoNormal"> for(i = 1, cnt = 0; i <= n; i++) cnt += f[m][n][i];</p> <p class="MsoNormal"> return cnt;</p> <p class="MsoNormal"><span lang="ZH-CN">可见，这是一个</span>O(n^3*m)<span lang="ZH-CN">的算法，仅适合规模小的情况</span></p> <p class="MsoNormal">(2) <span lang="ZH-CN">改进这个规划算法，减少第</span>3<span lang="ZH-CN">维的状态，</span>i<span lang="ZH-CN">，</span>j<span lang="ZH-CN">的状态含义有改变，它们此时的含义就是：将整数</span>i<span lang="ZH-CN">划分为</span>j<span lang="ZH-CN">份的方案数。根据类似于</span>“<span lang="ZH-CN">堆积木</span>”<span lang="ZH-CN">的思维，当前状态实际上就是现在最下一行各摆上</span>“1”<span lang="ZH-CN">块积木接下来就是把</span>“i-j”<span lang="ZH-CN">块积木放上去并保持阶梯状，实际就是</span>“i-j”<span lang="ZH-CN">拆分成</span>“0~k(k <= j)”<span lang="ZH-CN">份的方案总数之和，所以有：</span>f[i][j] = SUM{ f[i-j][k] | 0 <= k <= j}</p> <p class="MsoNormal"> for (i = 1; i <= n; i++)</p> <p class="MsoNormal"> for (j = 1; j <= (i > m ? m : i); j++)</p> <p class="MsoNormal"> for (k = 0; k <= j; k++)</p> <p class="MsoNormal"> f[i][j] += f[i-j][k]</p> <p class="MsoNormal"> return f[n][m];</p> <p class="MsoNormal"> <span lang="ZH-CN">可见，这是一个</span>O(n*m^2)<span lang="ZH-CN">的算法，仍然不怎么适用于大规模的</span>n, m</p> <p class="MsoNormal">(3) <span lang="ZH-CN">是否可以继续化简呢？可以从方程入手，<strong>首先我们要有一个概念，那就是</strong>：<span style="text-decoration: underline;">如果</span></span><span style="text-decoration: underline;">DP</span><span style="text-decoration: underline;"><span lang="ZH-CN">中要用到对前面状态求和，那么要么可以</span></span><span style="text-decoration: underline;">O(n^2)</span><span style="text-decoration: underline;"><span lang="ZH-CN">预处理</span></span><span style="text- |
|
转播
