动态规划——【转】划分数问题



<pre>
整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分,是指把一个正整数n写成如下形式:</br></br>
n=m1+m2+...+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,m2,...,mi}为n的一个划分。</br></br>
如果{m1,m2,...,mi}中的最大值不超过m,即max(m1,m2,...,mi)<=m,则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);</br></br>
例如但n=4时,有5个划分,{0,0,0,4},{0,0,3,1},{0,0,2,2},{0,2,1,1},{1,1,1,1};</br></br>
注意{0,0,1,3} 和 {0,0,3,1}被认为是同一个划分。</br></br>
该问题是求出n的所有划分个数,即f(n, n)。下面我们考虑求f(n,m)的方法;
</pre></br>

<a>递归法</a></br>

根据n和m的关系,考虑以下几种情况:</br>
(1)当 n = 1 时,不论m的值为多少(m > 0 ),只有一种划分即 { 1 };
<pre><code> 因此 f(1, m) = 1;</code></pre></br>
(2)当 m = 1 时,不论n的值为多少,只有一种划分即 n 个 1,{ 1, 1, 1, ..., 1 };</br>

<pre><code> 因此 f(n, 1) = 1;</code></pre></br>
(3)当 n = m 时,根据划分中是否包含 n,可以分为两种情况:
a. 划分中包含n的情况,只有一个即 { n };
b. 划分中不包含n的情况,即划分中最大的数字也比 n 小,也就是 n 的所有 ( n - 1 ) 划分。
<pre><code> 因此 f(n, n) = 1 + f(n, n-1);</code></pre></br>
(4)当 n < m 时,由于划分中不可能出现负数,因此就相当于 f(n, n), 转至第三种情况;</br></br>
(5) 但 n > m 时,根据划分中是否包含最大值 m,可以分为两种情况:
a. 划分中包含 m 的情况,即 { m, { x1, x2, ..., xi } }, 其中 { x1, x2, ..., xi } 的和为 (n - m),可能再次出现 m,因此是(n - m)的 m 划分,因此这种划分个数为 f(n-m, m);
b. 划分中不包含 m 的情况,则划分中所有值都比 m 小,即 n 的 ( m - 1 ) 划分,个数为 f(n, m - 1);
<pre><code> 因此 f(n, m) = f(n - m, m) + f(n, m - 1);</code></pre>
综合以上情况,我们可以看出,上面的结论具有递归定义特征,其中(1)和(2)属于回归条件,(3)和(4)属于特殊情况,将会转换为情况(5)。而情况(5)为通用情况,属于递推的方法,其本质主要是通过减小m以达到回归条件,从而解决问题。其递推表达式如下:
<pre><code>
f(n, m) = 1; ( n = 1 or m = 1 )
f(n, n); ( n < m )
1+ f(n, m - 1); ( n = m )
f(n - m, m) + f(n, m - 1); ( n > m )
</code></pre>
</br>
给出代码如下(c/c++实现)
<pre>
<code>
int f(int i, int j)
{
int ret;
if (j == 1 || i == 1)//情况(1),(2)
return 1;
else if (i == j)//情况(3)
ret = 1 + f(i,j-1);
else if (i < j)//情况(4)
ret = f(i, i);
else if (i > j)//情况(5)
ret = f(i-j,j) + f(i,j-1);
return ret;
}
</code>
</pre>
</br>
注:本文原稿摘自http://www.cnblogs.com/hoodlum1980/archive/2008/10/11/1308493.html

推荐阅读更多精彩内容

  • 整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分,是指把一个正整...
    Ethan_Walker阅读 1,578评论 0 1
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 165,874评论 24 701
  • 夜凉如水,窗外熙攘了一天的街道,也渐渐安静下来,只有路灯还在孤独的亮着,偶尔有几辆车疾驰而过。 一盏台灯,一台电脑...
    官官官大人阅读 606评论 8 8
  • 一套减肥产品你心疼❓ 喜欢的衣服穿不上心疼么 闺蜜比你瘦 心疼么 走在大街上 前后比你瘦的都比你美心疼么️ 人家3...
    用一生de爱去演绎阅读 275评论 0 0
  • 经过漫长且压抑的深秋 阴雨绵绵的日子也总算告一段落了 冬日里的一缕阳光穿过树梢 透过窗户 毫无防备地洒在头发上变成...
    落尘rome阅读 110评论 0 1
  • 潜龙 勿用 待何日 吟啸九霄归碧空, 苍茫大地起飞尘 指点江山 红尘掩碧空 大浪淘沙 半江金砾辉煌。 星移...
    四十二客星阅读 87评论 0 0