区间dp
什么是区间dp?
顾名思义:区间dp就是在区间上进行动态规划,求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。
思路
既然让我们求一个区间上的最优解,那我们就可以把一个长区间分为许多个小区间,求出每个小区间的最优解,然后再合并。
伪代码
for(int len = 1;len <= n;len++){//枚举长度
for(int j = 1;j + len - 1 <= n;j++){//枚举起点,ends<=n
int ends = j + len - 1;
for(int i = j;i < ends;i++){//枚举分割点,更新小区间最优解
dp[j][ends] = min(dp[j][ends],dp[j][i] + dp[i+1][ends] + something);
}
}
}
经典例题
[石子合并](石子合并 - 蓝桥云课 (lanqiao.cn))
根据区间dp的思想我们可以得出状态转移方程
dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
这部分是dp[i][k] + dp[k + 1][j]两个区间合并的最优解的和。还要加上本次合并消耗的费用。
我们需要计算从 i 到 k 的总费用,但是一个一个相加显然是很费时间的,因此我们需要用到前缀和数组,这是经常用到的一种优化。
sum[i] = sum[i - 1] + num[i];
题解代码:
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int max = 0x3f3f3f3f;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
//石子数组
int[] num = new int[n+1];
//石子堆数组
int[] sum = new int[n+1];
//记忆化数组,用来记录总的代价
int[][] dp = new int[n+1][n+1];
//dp数组初始化
for(int i=0;i<=n;i++) {
Arrays.fill(dp[i],max);
}
sum[0] = 0;
//sum数组初始化
for(int i=1;i<=n;i++) {
num[i] = sc.nextInt();
sum[i] = num[i] + sum[i-1];
dp[i][i] = 0;
}
//第一层len代表区间长度
// 两堆合并,区间长度从2开始
for(int len = 2; len <= n; len++) {
//第二层i代表区间开头
for(int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
//第三层k代表区间分割的位置
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]);
}
}
}
//即代表1-n石子的最小代价
System.out.println(dp[1][n]);
}
}
}