Two Sets II动态规划问题：dp[n-1][maxSum]替代dp[n][maxSum]/2的原理

原有代码的错误原因 #

你的动态规划定义dp[i][j]表示从1~i的数字中选出若干个，和为j的子集方案数。
当你算到dp[n][maxSum]的时候，得到的是所有1~n中和为总和一半的子集数量。这里面每一种合法的集合划分都被统计了两次：比如划分{A,B}，选A子集算一次，选B子集也算一次，所以理论上你需要将结果除以2得到正确的划分方案数。
但你直接用了整数除法/2，这里存在严重问题：你所有的dp值都是对1e9+7取模后的结果，模运算下不能直接做普通整数除法，只有乘以除数的模逆元才是正确操作。比如当模后的值为奇数时，普通整数除法会直接截断得到错误结果，这就是你5个测试用例不通过的根本原因。

修改为dp[n-1][maxSum]的原理 #

这个修改的核心是通过固定元素归属避免重复计数，从根源上消除了除法操作：

• 我们可以人为约定数字n固定属于第二个集合，不放入我们统计的子集里
• 此时我们只需要统计从1~n-1中选出和为maxSum的子集数量即可：选出来的子集作为第一个集合，剩下的元素（包含n）自动构成第二个和为maxSum的集合
• 这种统计方式下，每一种合法划分只会被计数一次，不存在重复，所以不需要再除以2，也完全避开了模运算除法的坑
  比如示例n=7的场景：maxSum=14，dp[6][14]统计的就是从1~6里选和为14的子集数，刚好等于4，和示例的正确结果完全一致。

额外补充：另一种可行的修改方式 #

你也可以不修改dp的取值，只把输出的除法换成乘以2的模逆元即可，因为1e9+7是质数，2的逆元为500000004，修改后的输出语句为：

cout << dp[n][maxSum] * 500000004 % 1000000007 << endl;

这种方式和用dp[n-1][maxSum]得到的结果是完全等价的。

内容的提问来源于stack exchange，提问作者WilliamHarvey