#include <bits/stdc++.h>
using namespace std;
long long n,f[1000][1000],sum[50];
int main()
{
	cin >> n;
	for(int i=1; i<= n ;i++)
	{
		sum[i] = sum[i-1] + i;
	}
	if(sum[n] % 2 == 1)
	{
		cout << 0;
		return 0;
	}
	f[0][0] = 1;// 前k个数 分成i j两堆，i，j的个数
	for(int k=1; k<= n ;k++)
	{
	    for(int i = sum[k]; i >= 0; i--)//背包变形
		{
			for(int j=sum[k];j >= 0; j--)
			{
				if(i >= k)
				    f[i][j] += f[i-k][j];
				if(j >= k)
					f[i][j] += f[i][j-k];
			}
		}
	}
	cout << f[sum[n]/2][sum[n]/2]/2;
}

洛谷本题传送门

不是很擅长动态规划类型的题，所以也是参照了洛谷大神的方法来做一做，我也明白了

毕竟不是完全靠自己想出来的，所以写成读后感

1.这是一道求总数量的动态规划题
2.一个数分选和不选两种可能
3.如果dfs时间复杂度是O(2^n)(亲测n最多取到24，往上就超时了)
4.可以使用二维动态规划对每个状态单独求解
5.如果1一直加到n为奇数一定没有情况
f[ i ][ j ]即表示在前i个数里面取数，总和为j的情况总数(可能会非常大，就需要开long long)
注意初始状态f[ 0 ][ 0 ]为1
6.完整代码见下

#include<bits/stdc++.h>
using namespace std;
int n , ans , flag[ 40 ] , sum[ 40 ];
long long f[ 40 ][ 2000 ] ;
int main()
{
    ios::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cin >> n ;
    for( int i = 1 ; i <= n ; i ++ ) sum[ i ] = sum[ i - 1 ] + i ;
    if( sum[ n ] % 2 != 0 )
    {
        cout << 0 ;
        return 0 ;
    }
    f[ 0 ][ 0 ] = 1 ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        for( int j = 1 ; j <= sum[ n ] ; j ++ )
        {
            f[ i ][ j ] = f[ i - 1 ][ j ] + f[ i - 1 ][ j - i ] ;
        }
    }
    cout << f[ n ][ sum[ n ] / 2 ] ;
    return 0;
}