文章目录

题意

问题描述:将1到N的连续整数组成的集合划分为两个子集合,且保证每个集合的数字和相等。例如,对于N=4,对应的集合{1,2,3,4},能被划分为{1,4}、{2,3}两个集合,使得1+4=2+3,且划分方案只有此一种。编程实现给定任一正整数N(1<=N<=39),输出其符合题意的划分方案数。

样例输入1:3

样例输出1:1    (可划分为{1,2}、{3})

样例输入2:4

样例输出2:1    (可划分为{1,3}、{2,4})

样例输入3:7

样例输出3:4    (可划分为{1,6,7}、{2,3,4,5},或{1,2,4,7}、{3,5,6},或{1,3,4,6}、{2,5,7},或{1,2,5,6}、{3,4,7})

思路

根据动态规划思想,可以得到状态转移方程如下:

[code lang=”php”]
$d[$i][$j] = $d[$i – 1][$j] + $d[$i – 1][$j – $i];
// $i 取前$i个元素
// $j 取前$i个元素总和为$j
// $d[$i][$j] 取前$i个元素总和为$j的方案数
[/code]

如果,对动态规划不理解建议看下这个视频:http://open.163.com/movie/2010/6/8/1/M6TCSIN1U_M6TCT9E81.html
状态转移方程:取$i个元素的方案数为$d[$i – 1][$j],不取第$i个元素的方案数为$d[$i – 1][$j – $i]。故将$i的问题递归为$i – 1的问题。符合动态规划的基本思想:
1. overlapping sub-problem(重叠子问题)
2. optimal sub-structure (最优子结构)

源码

方案一:

[code lang=”php”]
function t2($n) {
$sum = ($n + 1) * $n / 2;
if($sum % 2) {
return 0;
}
$sum = $sum / 2;
$t = array();
for($i = 0; $i <= $n; $i++) {
for($j = 0; $j <= $sum; $j++) {
if($j == 0) $d[$i][$j] = 1; else $d[$i][$j] = 0;
}
}
for($i = 1; $i <= $n; $i++) {
for($j = 1; $j <= $sum; $j++) {
$d1 = $d[$i – 1][$j];
$d2 = $d[$i – 1][$j – $i];
$d[$i][$j] = $d1 + $d2;
// echo "i:{$i} j:{$j} d1(d[{$i} – 1][{$j}]):{$d1} d2(d[{$i} – 1][{$j} – {$i}]):{$d2}\n";
}
}
// var_dump($d);
return $d[$n][$sum] / 2;
}
[/code]

 

方案二:

[code lang=”php”]
<?php
function t($n) {
$sum = ($n + 1) * $n / 2;
if($sum % 2) {
return 0;
}
$sum = $sum / 2;
$d = array();
$d[0] = 1;
for($i = 1; $i <= $n; $i++) {
for($j = $sum; $j >= $i; $j–) {
// echo "j:{$j} i:{$i}\n";
// echo "the j – 1 is: {($j-$i)}\nthe d[j – i] is: {$d[$j – $i]}\n";
$d[$j] += $d[$j – $i];
// var_dump($d) . "\n\n";
}
}
// echo "rs:" . var_dump($d);
return $d[$sum] / 2;
}
[/code]

可以看出第二种的优化相对于第一种在空间复杂度上有了很大的提升。
V = N * (N + 1) / 4
第一种:O(N * V) = O( N^2 * (N+1) / 4)
第二种:O(N)


建议参考文章:http://www.cnblogs.com/kangjianwei101/p/5332451.html

文章来源:胡旭个人博客 => 【原】拆分集合为两个和相等的两个子集合的问题(动态规划)

转载请注明出处,违者必究!

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.