imicola 区间DP
区间DP

区间DP

529 字 · 约 1 分钟

引入

  • 给定一堆长度为 nn 的石子,每个石子有其重量 aia_i ,你需要做的是不断的合并相邻石子,每次合并i,ji,j两堆石子需要付出 ai+aja_i + a_j的代价,你必须不断合并直到所有石子均被合并完成。你需要知道你付出的最小代价是多少

特点

  • 区间dp的特点我们一般认为有以下
    • 在某一个序列上的一个区间进行操作,如(合并)
    • 可以利用子区间的最优解来构造全局的最优解

dp含义以及状态转移

状态定义:

  • 区间状态,我们定义dp[ i ][ j ]dp[\,i \,][\,j\,]表示从位置 ii 到位置 jj 的最优解(最小代价,最大收益等)
  • 对于每一个 dp[ i ][ j ]dp[\,i\,][\,j\,] 我们都应该保证其状态能从子区间转移而来

状态转移:

  • 区间划分:为了计算dp[ i ][ j ]dp[\,i\,][\,j\,],我们往往需要一个中间值 k∈[ i,j )k \in [\,i,j\,)
    • kk将区间[ i,j ][\,i,j\,]划分为两个区间 [ i,k ][\,i,k\,] 和 [ k+1,j ][\,k+1,j\,]
    • 我们通过合并这两个子区间的代价来进行选择
    • 为了能够知道所有状态的最优解,kk应该遍历[ i,j )[\,i,j\,)
  • 递推式
    dp[ i ][ j ]=min⁡i≤k<j{dp[ i ][ k ]+dp[ k+1 ][ i ]+cost(i,k,j)}dp[\,i\,][\,j\,] = \underset{i\le k < j }\min{\{dp[\,i\,][\,k\,] + dp[\,k+1\,][\,i\,] + \mathrm{cost}(i,k,j)\}}
  • 其中 cost(i,j,k)\mathrm{cost}{(i,j,k)} 为合并两个子区间所产生的代价

dp计算思路

  • 一般区间dp有三层for循环,第一层枚举长度 lenlen ,第二次找区间起始点 ii ,第三层遍历所有中间点 kk

一般模板代码

我们以引入问题为例进行分析

vector<vector<int>> dp(N,vector<int>(N));
// 我们认为序列长度有n
for(int i = 1 ; i <= n ; i++){
	dp[i][i] = 0;
}
// 预处理,根据题目含义做出预处理数组(前缀和,或合并代价)(此处为合并石子,即石子的前缀和,用于计算区间代价)
vector<int> vv(N);
for(int i = 1; i <= n; i++) {
	vv[i] = vv[i-1] + v[i];
}

//进行区间dp,枚举所有长度n
for(int len = 2;len <= n; len++){            //第一层,枚举长度
	for(int i = 1; i + len - 1 <= n; i++){   //第二层,枚举起点
		int j = i + len - 1;                 //计算终点
		dp[i][j] = INT_MAX;                 
		for(int k = i; k < j ;k++{
			dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + (vv[j] - vv[i-1]);       // 区间dp转移,遍历所有中间节点,取最小值
		}
	}
}

cout << dp[1][n];         //答案即为从1-n的区间最优解
cpp