目录

zrlong 的个人博客

希望大家都能保护好自己身上的特质,无论是五年还是十年,永远善良,不服输,热爱你所热爱。在漫长岁月的变迁里,是这些让你永远迷人,富有生命力。

X

区间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]);

image.png

这部分是dp[i][k] + dp[k + 1][j]两个区间合并的最优解的和。还要加上本次合并消耗的费用。

image.png

我们需要计算从 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]);
        }
    }
}

标题:区间dp
作者:zrlong
地址:http://blog.zrlong.top/articles/2022/04/08/1649403631105.html