动态规划解决部分和问题（java）

朱雀 2021-03-23 14:51 575阅读 0赞

题目：晓萌希望将1到N的连续整数组成的集合划分成两个子集合，且保证每个集合的数字和是相等。例如，对于N=3，对应的集合\{1，2，3\}能被划分成\{3\} 和 \{1,2\}两个子集合.

这两个子集合中元素分别的和是相等的。

对于N=3，我们只有一种划分方法，而对于N=7时，我们将有4种划分的方案。

输入包括一行，仅一个整数，表示N的值（1≤N≤39）。

输出包括一行，仅一个整数，晓萌可以划分对应N的集合的方案的个数。当没发划分时，输出0。

样例输入

7  
样例输出

--------------------

分析： 划分成两部分，那么这两部分的值也就是可以确定的，值为N! / 2。

所以N! 只有是偶数的话才可分。
      也就是本题可以转化为部分和问题，即前N个数的和能凑成N! / 2的有多少种。
      注意的是 {1, 2} {3}和{3} {1, 2}为一种。
      设 dp[i][j]前i个数的部分和可以凑成j的子集数
      动态转移方程：
      当j >= arr[i - 1]时 dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j]
      其他： dp[i][j] = dp[i - 1][j]

代码实例：

Scanner read = new Scanner(System.in);
            int N = read.nextInt();
            int sum = N * (N + 1)/ 2;
            if((sum & 1) == 1)// 如果和为奇数时  不可分
                System.out.println("0");
            else{
                // dp[i][j] 前i个数的部分和可以凑成j的子集数
                long[][] dp = new long[N +1][(sum / 2) + 1];
                //0可以凑成0
                dp[0][0] = 1;
                for(int i = 1; i <= N; ++i){
                    for(int j = 0; j <= sum / 2; ++j){
                        if(j >= i){//当j >= arr[i - 1]时  dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j];
                            dp[i][j] = dp[i - 1][j - i] + dp[i - 1][j];
                        }else{//其他： dp[i][j] = dp[i - 1][j];
                            dp[i][j] = dp[i - 1][j];
                        }
                    }
                }
                // 计数过程中类似的  {1, 2} {3}和{3} {1, 2} 会被重复记录 所以除2
                System.out.println(dp[N][sum / 2] / 2);
            }