西宁做网站_君博示范,有哪些专门做写字楼的网站,做电商网站需要会些什么,国家企业信用信息公示系统河北文章目录 一、适用场景二、基本思路步骤时间复杂度#xff1a; 三、例题 区间动态规划#xff08;Interval DP#xff09;是一种用于解决某些需要处理区间或子段问题的动态规划方法#xff0c;特别适合于问题的解可以通过子区间的解进行组合的情况。该方法的核心思想是在子… 文章目录 一、适用场景二、基本思路步骤时间复杂度 三、例题 区间动态规划Interval DP是一种用于解决某些需要处理区间或子段问题的动态规划方法特别适合于问题的解可以通过子区间的解进行组合的情况。该方法的核心思想是在子区间上进行分治将大问题划分为较小的子问题通过解决这些子问题来构建整个问题的解。 一、适用场景
区间 DP 主要用于解决一些涉及区间或序列的问题。这类问题通常要求在一个序列上做某种操作如合并、拆分、重排等并且这些操作的结果取决于其子区间的操作结果。常见的应用包括
石子合并问题合并区间。括号匹配问题。最优矩阵连乘问题。回文分割问题。
二、基本思路
区间 DP 的核心是通过枚举区间的分割点将问题分解为两个或多个子区间的问题。解决每个子区间的问题后再通过这些子区间的解组合得到整个区间的解。
步骤
定义状态 设 dp[i][j] 表示在区间 [i, j] 上的最优解。 状态转移方程 根据问题的性质找到合适的分割方式通常是选择一个分割点 k将区间 [i, j] 分为 [i, k] 和 [k1, j] 两个部分并通过已知的子区间解来更新 dp[i][j]。一般形式的状态转移方程为 d p [ i ] [ j ] min i ≤ k j ( d p [ i ] [ k ] d p [ k 1 ] [ j ] 合并代价 ) dp[i][j] \min_{i \leq k j} (dp[i][k] dp[k1][j] 合并代价) dp[i][j]i≤kjmin(dp[i][k]dp[k1][j]合并代价) 其中 k 是区间的分割点合并代价 由具体问题定义。 初始状态 最小区间的解例如当 i j 时区间仅包含一个元素通常可以直接得到最优解。 结果 最终目标是通过填充 dp 数组找到 dp[1][n]即整个区间 [1, n] 的最优解。
时间复杂度
区间 DP 的时间复杂度取决于问题的规模。对于每个区间 [i, j]需要遍历所有的分割点 k这通常需要三层循环因此复杂度为 O ( n 3 ) O(n^3) O(n3)其中 n 是序列的长度。
三、例题
Acwing282.石子合并 这是一个经典的区间dp的问题。根据前面的描述我们可以知道区间dp实际上就是将整个区间问题转化成多个区间子问题然后状态转移至整个区间。
这里所说的石子合并就是将两个子区间合并成一个大区间。 我们将石子合并成一堆那么在前一步一定是两堆合并而来的那么这两堆分别又是一个子问题实际上动态规划也是处理子问题到整个问题转移的算法。
我们可以定义 d p [ i ] [ j ] dp[i][j] dp[i][j]表示从初始开始编号为i 1 ~ j 1的石子合并成一堆的最小代价。那么必然有 d p [ i ] [ j ] d p [ i ] [ k ] d p [ k 1 ] [ j ] m [ j ] − m [ i − 1 ] dp[i][j] dp[i][k] dp[k1][j] m[j] - m[i - 1] dp[i][j]dp[i][k]dp[k1][j]m[j]−m[i−1]其中ikj。
我们可以发现动态规划实际上就是带有记忆的搜素。这里我们并不知道哪个子问题合并起来才是最优的因此我们遍历所有可能得子区间划分情况来求解。由这个递推我们从小区间到大区间依次求值。
注意合并才有代价单个石子代价为0。 时间复杂度 O ( N 3 ) O(N^3) O(N3)
#includebits/stdc.h
using namespace std;
int main(void){ios_base::sync_with_stdio(false);cin.tie(0);int N; cin N;vectorint m(N, 0);vectorvectorint dp(N, vectorint(N, 0x3f3f3f3f));cin m[0]; dp[0][0] 0;for(int i 1; i N; i){cin m[i];m[i] m[i - 1];dp[i][i] 0;}for(int i 1; i N; i){for(int j 0; j i N; j){int p i j;for(int k j; k p; k){if(j ! 0)dp[j][p] min(dp[j][p], dp[j][k] dp[k 1][p] m[p] - m[j - 1]);else dp[j][p] min(dp[j][p], dp[j][k] dp[k 1][p] m[p]);}}}cout dp[0][N - 1];return 0;
}
