```cpp
cout<<dp[sum/2];
```
@[penjiexiaodi](/user/612360) 我眼花了？没除吗？
by _5555_ @ 2022-06-17 17:04:44
@[Black_Mamba_R](/user/722330) 他说的是答案，划分集合的方式为什么不要除以二。
by irris @ 2022-06-17 17:22:23
@[AlgorithmerSnow](/user/419487) 是的，答案没除却对了
by muhouchen @ 2022-06-17 17:45:19
@[penjiexiaodi](/user/612360) 貌似只要把i改为1时就要/2;
```cpp
for(int i=2;i<=n;i++)
for(int j=sum;j>i;j--)
dp[j]+=dp[j-i];
```
```cpp
for(int i=1;i<=n;i++)
for(int j=sum;j>i;j--)
dp[j]+=dp[j-i];
```
额,我也不怎么懂.
by gzy_YHL @ 2022-07-16 20:14:10
@[gzy_YHL](/user/576913) 对滴，我先把这两种都试了下
by muhouchen @ 2022-07-16 21:22:39
好神奇，为什么这个程序是正确的呀？
by 吃不饱QAQ @ 2022-11-29 01:25:50
@[muhouchen](/user/612360) @[gzy_YHL](/user/576913) @[吃不饱QAQ](/user/416021)
我磕了很久，找到了部分原因（来自蓝名的倔强
缺了`dp[0] = 1`。
**以下均以样例来说明（即输入7）**
$i$ 从1开始循环时，如果初始时有 $dp_1=1$ 但没有 $dp_0=1$，在 $i = 1$的第一轮循环结束后，会出现 $dp_2=dp_1=1$，这是不对的。
事实上，如果 $i$ 从1开始，我们需要的是 $dp_0=1$，不需要 $dp_1=1$ ，因为在第一轮循环中 $dp_1=dp_1+dp_0=1$ ，这种情况下结果需要除以2，也符合我们的逻辑。
------------
$i$ 从2开始，$dp_0=1$ 和 $dp_1=1$ 都是需要的。需要 $dp_0=1$ 的原因同上；需要 $dp_1=1$ 也很简单就不说了。这种情况也是需要除以2的。
------------
## 真正的问题是为什么在没有 $dp_0=1$ 仅仅有 $dp_1=1$ 的情况下为什么答案就正好是一半不需要除以2了。
先输入7，把二维的 $dp$ 打出来。
第一份代码：
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int n;
long long dp[10000];
int main()
{
cin >> n;
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
for (int j = n * (n + 1) / 4; j >= i; j--)
dp[j] += dp[j - i];
cout << i << " ";
for (int j = 1; j <= n * (n + 1) / 4; j++)
cout << dp[j] << " ";
cout << "\n";
}
return 0;
}
```
第二份代码（把`dp[0] = 1`去掉）：
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int n;
long long dp[10000];
int main()
{
cin >> n;
// dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
for (int j = n * (n + 1) / 4; j >= i; j--)
dp[j] += dp[j - i];
cout << i << " ";
for (int j = 1; j <= n * (n + 1) / 4; j++)
cout << dp[j] << " ";
cout << "\n";
}
return 0;
}
```
输入7得到的结果分别为：
```
2 1 1 1 0 0 0 0 0 0 0 0 0 0 0
3 1 1 2 1 1 1 0 0 0 0 0 0 0 0
4 1 1 2 2 2 2 2 1 1 1 0 0 0 0
5 1 1 2 2 3 3 3 3 3 3 2 2 1 1
6 1 1 2 2 3 4 4 4 5 5 5 5 4 4
7 1 1 2 2 3 4 5 5 6 7 7 8 8 8
```
```
2 1 0 1 0 0 0 0 0 0 0 0 0 0 0
3 1 0 1 1 0 1 0 0 0 0 0 0 0 0
4 1 0 1 1 1 1 1 1 0 1 0 0 0 0
5 1 0 1 1 1 2 1 2 1 2 1 1 1 0
6 1 0 1 1 1 2 2 2 2 3 2 3 2 2
7 1 0 1 1 1 2 2 3 2 4 3 4 4 4
```
注意到一个有意思的现象，那就是第一张表中所有的偶数在第二张表中都除以了2.
这就说不清是为什么了，我想破头都没想明白，得请数学神犇来
by lzy20091001 @ 2023-08-02 12:09:48
@[muhouchen](/user/612360) @[gzy_YHL](/user/576913) @[吃不饱QAQ](/user/416021)
发现了一个反例QwQ
最后一行，从右往左数第六个，第一张表里是6，第二张表里是2。
这说明不是对应的？
那只能用碰巧AC来解释了？（感觉又不太像？）
by lzy20091001 @ 2023-08-02 20:12:59
@[lzy20091001](/user/932039) 我有一个想法，就是说dp[j]的定义是取出的数的和为j的方案数，那么i从2开始的话就表示我们第一个序列里是绝对不包含1的，也就是说1一定就在第二个序列里。
然后在设想一下，如果不对序列的划分做要求的话，那么每个数都有两种放法：放在第一个集合或放在第二个集合。总方案数为2^n。
所以，我们规定一个数所在的集合后，总方案数就要除以2
by Parrhesiates @ 2023-08-02 20:46:40
@[liuyidu](/user/519824) 不过有个问题，在题设情景下，1和别的数地位不是对等的，这可能是导致那个反例的原因。
by Parrhesiates @ 2023-08-02 21:00:52