拆分集合为两个和相等的子集合问题(动态规划)

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