代码很短。

#include <iostream>
#include <cmath>

using namespace std;

const int N=2003;
const long long INF=1000000000000ll;

int n; 
long long f[N][N];
bool vis[N][N];

long long dp(int x,int h) {
	if(h<int(ceil(log2(x+1))) || h>x)
		return INF;
	if(vis[x][h])
		return f[x][h];
	
	vis[x][h]=true;
	for(int i=1;i<=x/2;i++) {
		long long tmp=dp(x-i-1,h-1);
		f[x][h]=min(f[x][h],min(dp(i,h-1)+tmp+i,dp(i,h-2)+tmp+i));
	}
	
	return f[x][h];
}

int main() {
	ios::sync_with_stdio(false);
	
	cin>>n;
	
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			f[i][j]=INF;
	
	vis[1][1]=vis[2][2]=true;
	f[1][1]=f[2][2]=0;
	
	long long ans=INF;
	for(int i=1;i<=n;i++)
		ans=min(ans,dp(n,i));
	cout<<ans<<endl;
}

$n=2000$ 在学校电脑上跑了 3min 才出结果，抱着试一试的心态交了一发，开不开 O2 都跑得飞快，直接过了。
想知道是触发了什么 UB 还是学校电脑太差。编译器是 MinGW64 11.2.0，电脑配置是 Intel(R) Core(TM) i3-4130 CPU @ 3.40GHz 3.40 GHz，4GB RAM（其实我不会看）。