區(qū)間dp
2022-08-29 23:56:17

區(qū)間dp一般是
形如 dp[i][j] = oper(dp[i][k],dp[k+1][j] ) + cost[i..j];
其中 oper可能是 求最大最小值，或乘法或加法，等等。
的dp
有一個比較簡單題，可以對區(qū)間dp有個基本的了解https://www.acwing.com/problem/content/284/
此題思路如圖所示

ac代碼如下

#define NMAX 303

int nums[NMAX];
int sum[NMAX];
int dp[NMAX][NMAX];

int main(){
	int N;
	scanf("%d",&N);
	for(int i=0;i<N;++i){
		scanf("%d",&nums[i]);
	}
	for(int i=1;i<=N;++i){
		sum[i] = sum[i-1] + nums[i-1];
	}

	for(int l=2;l<=N;l++){
		for(int i=0;i+l-1<N;++i){
			int j = i+l-1;
			int tmp = INT_MAX;
			for(int k=i;k<j;++k){
				tmp = min(tmp,dp[i][k]+dp[k+1][j]);
			}
			dp[i][j] = tmp + sum[j+1] - sum[i];
		}
	}
	printf("%d
",dp[0][N-1]);
	
	return 0;
}