看到方案数，果断想到 DP 。设 $dp_{i,j,0/1}$ 表示总和为 $i$ ，最后一个数为 $j$ ，该变大还是变小。不难列出方程

$dp_{i,j,0}=\sum_{k=1}^{j-1} dp_{i,j,1}$ $dp_{i,j,1}=\sum_{k=j+1}^n dp_{i,j,0}$

此时若直接转移时间复杂度为 $O(n^3)$ ，会超时。考虑优化，发现 $\sum$ 部分可以使用前缀和优化。

实现时，注意特判 $n=k$ 的时候，然后可以不用开 long long，因为只有加法，没有乘法。时空复杂度均为 $O(n^2)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
const int mod=1e9+7;
int dp[N][N][2],g[N][N][2];//g是前缀和数组
signed main(){
	int n,k,ans=0;
	cin>>n>>k;
	if(n==k){
	    cout<<1;
	    return 0;
	}
	dp[k][k][0]=dp[k][k][1]=1;
	for(int i=1;i<=n;i++){
		g[k][i][0]=g[k][i-1][0]+dp[k][i][0];
		g[k][i][1]=g[k][i-1][1]+dp[k][i][1];
		g[k][i][0]%=mod,g[k][i][1]%=mod;
	}
	for(int i=k+1;i<=n;i++){
		for(int j=1;j<=i;j++){
			dp[i][j][0]=g[i-j][j-1][1];
			dp[i][j][1]=g[i-j][i][0]-g[i-j][j][0]+mod;
			dp[i][j][0]%=mod,dp[i][j][1]%=mod;
		}
		for(int j=1;j<=n;j++){
			g[i][j][0]=g[i][j-1][0]+dp[i][j][0];
			g[i][j][1]=g[i][j-1][1]+dp[i][j][1];
			g[i][j][0]%=mod,g[i][j][1]%=mod;
		}
	}
	cout<<(g[n][n][0]+g[n][n][1])%mod;
	return 0;
}