动态规划为什么是神

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
int a[1005], dp[1005], ct;
int solve(int n){
	memset(dp, 0, sizeof(dp));
	int ct = 0; 
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		ct += a[i];
	}
	for(int i = 1; i <= n; i++){
		for(int j = ct / 2; j >= a[i]; j--){
			int _1 = abs(ct / 2 - dp[j]), _2 = abs(ct / 2 - dp[j - a[i]] - a[i]);
			if(_1 > _2) dp[j] = dp[j - a[i]] + a[i];
		}
	}
	return max(ct - dp[ct / 2], dp[ct / 2]);
}
int main(){
	int n1, n2, n3, n4;
	cin >> n1 >> n2 >> n3 >> n4;
	cout << solve(n1) + solve(n2) + solve(n3) + solve(n4);

	return 0;
}

时间复杂度：$O(n * sum(a))$