区间dp(含模板及例题)
概述:区间dp:就是对于区间的一种动态规划,对于某个区间,它的合并方式可能有很多种,我们需要去枚举所有的方式,通常是去枚举区间的分割点,找到最优的方式(一般是找最少消耗)。例如:对于区间【i,j】,它的合并方式有很多种,可以是【i,i+1】和【i+2,j】也可以是【i,k】和【k+1,j】(其中i<k<j)……在合并区间时,一般会有消耗(根据题意去计算),状态转移方程就可以表示成:dp
概述:
区间dp:就是对于区间的一种动态规划,对于某个区间,它的合并方式可能有很多种,我们需要去枚举所有的方式,通常是去枚举区间的分割点,找到最优的方式(一般是找最少消耗)。
例如:对于区间【i,j】,它的合并方式有很多种,可以是【i,i+1】和【i+2,j】也可以是【i,k】和【k+1,j】(其中i <= k < j)……
在合并区间时,一般会有消耗(根据题意去计算),状态转移方程就可以表示成:
dp[i][j] = min(dp[i][j], dp[i,k] + dp[k+1][j] + 合并区间的消耗 ) (k是区间分割点)
for (int k = i; k < j; k++) { //枚举区间分割点
dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+合并区间的消耗);
}
模板:
通常都是先枚举区间长度,区间长度为1就不用合并,所以从2开始枚举,然后枚举左端点,那么右端点就为左端点加区间长度-1,再枚举分割点 k,最后计算不同分割点 k 的情况下,合并区间的消耗,dp[i][j]选择其中的最小消耗。(需要注意的是要记得根据题意给上初值)
for (int len = 2; len <= n; len++) {//先枚举区间长度
for (int i = 1; i+len-1 <= n; i++) {//再枚举区间左端点,左端点加区间长度为右端点,不能大于n
int j = i+len-1; //区间右端点
for (int k = i; k < j; k++) { //枚举区间分割点
dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+合并区间的消耗);
}
}
}
模板题:石子合并
设有 N 堆石子排成一排,其编号为 1,2,3,…,N。每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。例如有 4 堆石子分别为
1 3 5 2
, 我们可以先合并 、2 堆,代价为 4,得到4 5 2
, 又合并1,2 堆,代价为 9,得到9 2
,再合并得到 11,总代价为 4+9+11=24;如果第二步是先合并2,3 堆,则代价为 7,得到4 7
,最后一次合并代价为 11,总代价为 4+7+11=22。问题是:找出一种合理的方法,使总的代价最小,输出最小代价。
题目链接:石子合并
思路:这可以直接套模板,只需要去处理如何计算合并消耗,我们由题中可知两区间石子的总重量就是合并消耗,由此很自然地想到用前缀和来计算区间和。
代码:
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] dp = new int[n+1][n+1];
int[] sum = new int[n+1];
for (int i=1; i<=n;i++) {
sum[i] = sum[i-1] + sc.nextInt();//接收并计算前缀和
Arrays.fill(dp[i], (int)1e8);//先将所有元素赋值为一个很大的数,因为求的是最小值
dp[i][i] = 0; //合并区间长度为1的初始值为0
}
for (int len = 2; len <= n; len++) {//先枚举区间长度
for (int i = 1; i+len-1 <= n; i++) {//再枚举区间左端点,左端点加区间长度不能大于n
int j = i+len-1; //区间右端点
for (int k = i; k < j; k++) {//枚举区间分割点
dp[i][j] = Math.min(dp[i][j],
dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
}
}
System.out.println(dp[1][n]);
}
}
例题2:关路灯
某一村庄在一条路线上安装了 n 盏路灯,每盏灯的功率有大有小(即同一段时间内消耗的电量有多有少)。老张就住在这条路中间某一路灯旁,他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。
为了给村里节省电费,老张记录下了每盏路灯的位置和功率,他每次关灯时也都是尽快地去关,但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯,然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率,然后选择先关掉功率大的一边,再回过头来关掉另一边的路灯,而事实并非如此,因为在关的过程中适当地调头有可能会更省一些。
现在已知老张走的速度为 1m/s,每个路灯的位置(是一个整数,即距路线起点的距离,单位:m)、功率(W),老张关灯所用的时间很短而可以忽略不计。
请你为老张编一程序来安排关灯的顺序,使从老张开始关灯时刻算起所有灯消耗电最少(灯关掉后便不再消耗电了)。
链接:关路灯
思路: 本题与上一题的区别在于合并区间的消耗方式不同,为功率x时间,速度为1m/s,所以消耗又可表示为功率x移动距离,因为要记录上一次所在位置才能知道到走到现在位置的距离,所以增加一维空间dp[i][j][0]表示关完 i ~ j 时,老张站在 i 点,dp[i][j][1]表示关完 i ~ j 时,老张站在 j 点,他只有这两种站法,因为区间 [i , j] 要么是[i + 1, j]往左走一格得来的,此时站在 i 点,要么是[i , j-1]向右走一格得来的,此时站在 j 点。所以这里的区间合并可以转换为上一个区间向左或向右走一步。因此状态转移方程:
dp[i][j][0] = min(dp[i+1][j][0] + count(i, i+1, i+1, j, n), dp[i+1][j][1] + count(i, j, i+1, j, n));
dp[i][j][1] = min(dp[i][j-1][0] + count(i, j, i, j-1, n), dp[i][j-1][1] + count(j-1, j, i, j-1, n));
详解见:https://blog.csdn.net/Easenyang/article/details/124760843?spm=1001.2014.3001.5501
代码:
import java.util.Scanner;
public class Main {
static int[][][] dp = new int[51][51][2];
static int[] po = new int[51];
static int[] sum = new int[51];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), c = sc.nextInt();
for (int i = 1; i <= n; i++) {
po[i] = sc.nextInt();
sum[i] = sum[i-1] + sc.nextInt();//计算前缀和
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)//将dp数组都初始化为一个超大的值,因为我们求的是最小功耗
dp[i][j][0]=dp[i][j][1] = Integer.MAX_VALUE/3;
dp[c][c][0] = dp[c][c][1] = 0; //初始位置的功耗为0
for (int len = 2; len <= n; len++) {
for (int i = 1; i+len-1 <= n; i++) {
int j = i+len-1; //count方法用来计算合并消耗
dp[i][j][0] = Math.min(dp[i+1][j][0] + count(i, i+1, i+1, j, n),
dp[i+1][j][1] + count(i, j, i+1, j, n));
dp[i][j][1] = Math.min(dp[i][j-1][0] + count(i, j, i, j-1, n),
dp[i][j-1][1] + count(j-1, j, i, j-1, n));
}
}
System.out.println(Math.min(dp[1][n][0], dp[1][n][1]));
}
/**
* @param x, y 移动前、后的路灯位置
* @param l, r l~r的路灯都是关着的
* @param n 总路灯数
* @return (po[y]-po[x])相当于时间,(sum[n]-sum[r]+sum[l-1])为其他未关的灯的总功率
*/
public static int count(int x, int y, int l, int r, int n) {
return (po[y]-po[x]) * (sum[n]-sum[r]+sum[l-1]);
}
}
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)