devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

区间DP (Java) 解析/模板/案例_java dp

作者：我家自动化 | 2024-05-03 21:22:58

赞

踩

java dp

一. 区间DP简单介绍

        区间DP，是经常会用到的、解决区间问题的一种方法，经常以动态规划（dfs/记忆化搜索）的形式展现，最核心的思想就是枚举区间（枚举端点），寻找切割点，处理因切割点而产生的结果，进行区间累加或者选取个别区间，从而解决整体的问题。

二. 区间DP模板

枚举区间 

  1. class Solution {
  2.     public int 区间dp(int[] v) {
  3.         int n = v.length;
  4.         int[][] dp = new int[n][n];
  5.         //枚举区间长度
  6.         for(int len = 满足题目要求的最小值; len <= n; len++){
  7.             //枚举左端点
  8.             for(int L = 0; L+len-1 < n; L++){
  9.                 //枚举右端点
  10.                 int R = L + len - 1;
  11.                 //设置动态规划数组的初始值
  12.                 dp[L][R] = maxvalue;
  13.                 or
  14.                 dp[L][R] = minvalue;
  15.                 //枚举区间内的可能的切割点
  16.                 for(int k = L+1; k < R; k++){
  17.                     dp[L][R] = Math.min(dp[L][R], dp[L][k] ？ dp[k][R] ？ 因切割点而产生的特殊值);
  18.                 }
  19.             }
  20.         }
  21.         //返回规定的区间范围
  22.         return dp[0][n-1];
  23.         or
  24.         return dp[1][n]
  25.         or
  26.         others
  27.     }
  28. }

枚举端点

枚举端点的方法和枚举区间本质上都一样，有些题目反而用枚举端点的方法更容易思考

  1. class Solution {
  2.     public int 区间dp(int[] v) {
  3.         int[][] dp = new int[v.length][v.length];
  4.         //枚举左端点，左端点经常从大到小枚举，为什么请看下文
  5.         for(int i = v.length-3; i >= 0; i--){
  6.             //枚举右端点
  7.             for(int j = i+2; j < v.length; j++){
  8.                 //dp数组初始值
  9.                 dp[i][j] = Integer.MAX_VALUE;
  10.                 or
  11.                 dp[i][j] = Integer.MIN_VALUE;
  12.                 //枚举切割点
  13.                 for(int k = i+1; k < j; k++){
  14.                     dp[i][j] = Math.min(dp[i][j],dp[i][k]？dp[k][j]？因切割点而产生的特殊值);
  15.                 }  
  16.             }
  17.         }
  18.         return dp[0][v.length-1];
  19.     }
  20. }

三. 区间DP经典案例

1.leetcode1312 让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

  1. 输入：s = "mbadm"
  2. 输出：2
  3. 解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
  4.  
  5. 输入：s = "zzazz"
  6. 输出：0
  7. 解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

 此问题和leetcode 516 最长回文子序列属于同类题目[Ref. 3]：

" 求的是将 s 变成回文串需要添加的最少字符数，所以我们只用求最长回文子序列长度即可，然后字符串 s 中除去最长回文子序列，剩下的字符就是不构成回文子序列的字符，添加与其同等数量的字符，将 s 构成回文串。"

**leetcode 516 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

  1. 输入：s = "bbbab"
  2. 输出：4
  3. 解释：一个可能的最长回文子序列为 "bbbb" 。
  4.  
  5. 输入：s = "cbbd"
  6. 输出：2
  7. 解释：一个可能的最长回文子序列为 "bb" 。
  1. class Solution {
  2.     public int longestPalindromeSubseq(String s) {
  3.         int len = s.length();
  4.         int[][] dp = new int[len][len];
  5.         for(int i = len-1; i >= 0; i--){
  6.             dp[i][i] = 1;
  7.             for(int j = i+1; j < len; j++){
  8.                 if(s.charAt(i) == s.charAt(j)){
  9.                     dp[i][j] = dp[i+1][j-1] + 2;
  10.                 }
  11.                 else{
  12.                     dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
  13.                 }
  14.             }
  15.         }
  16.         return dp[0][len-1];
  17.     }
  18. }

此题详解：

子串和子序列问题-动态规划向_子串 子序列_ForwardSummer的博客-CSDN博客

 再看此题

  1. class Solution {
  2.     public int minInsertions(String s) {
  3.         int len = s.length();
  4.         int[][] dp = new int[len+1][len+1];
  5.         for(int i = len-1; i>= 0; i--){
  6.             dp[i][i] = 1;
  7.             for(int j = i+1; j < len; j++){
  8.                 if(s.charAt(i) == s.charAt(j)){
  9.                     dp[i][j] = dp[i+1][j-1] + 2;
  10.                 }
  11.                 else{
  12.                     dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
  13.                 }
  14.             }
  15.         }
  16.         return len-dp[0][len-1];
  17.     }
  18. }

 本题小结：

（1）dp[i][j] 代表从i到j的区间(左闭右闭)内最长的回文子序列的长度

（2）那么，当s.charAt(i) == s.charAt(j)，dp[i][j] = dp[i+1][j-1] + 2 

（3）当s.charAt(i) != s.charAt(j)，dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]) 

（4） 字符串 s 中除去最长回文子序列，剩下的字符就是不构成回文子序列的字符

2.leetcode1039 多边形三角剖分的最低得分

你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。

假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。

返回 多边形进行三角剖分后可以得到的最低分 。

  1. 1.边长为n的多边形形产生的三角形为n-2个,n>=3
  2.  
  3. 2.当边为5时，固定一个边当作底（比如4-5），选择一个顶点（比如2），
  4.   蓝色线表示的三角形将整个五边形分为三个部分。
  5.  
  6. 3.当边长为5时，知道当前三角形面积（蓝色部分），知道左右的三角形面积，
  7.   即可得到所有的三角形面积，进而求其和。
  8.  
  9. 4.当来到多边形，依然找到一个三角形（求出其面积），将三角形左右两边求出（S1+S2），
  10.   即可求所有的三角形构成的面积之和。
  11.  
  12. 5.求出所有的可能性，选择其中一个最小的。

枚举左右端点 DFS

  1.  
  2. class Solution {
  3.     int[] v;
  4.     public int minScoreTriangulation(int[] v) {
  5.         this.v = v;
  6.         return dfs(0,v.length-1);
  7.     }
  8.     public int dfs(int i, int j){
  9.         if(i+1 == j) return 0;
  10.         int res = Integer.MAX_VALUE;
  11.         for(int k = i+1; k < j; k++){
  12.             res = Math.min(res,dfs(i,k)+dfs(k,j)+v[i]*v[j]*v[k]);
  13.         }
  14.         return res;
  15.     }
  16. }

本方法小结：

（1）dfs的意义代表从i端点到j端点构成的多边形的最小面积，相当于上图的{1~N+N~1}（顺时针）

（2）以i和j为底，k为顶点的三角形会把整个多边形分成更小的子问题

（3）左边的子问题为dfs(i,k)，右边的子问题为dfs(k,j)，已经解决的问题为当前这个三角形，即为v[i]*v[j]*v[k]

（4）当i+1 == j时，只有两个点，构不成三角形，返回0

 DFS超时，因为算法复杂度是O(n^3)，数据很容易超时，接下来改成记忆化搜索。

记忆化搜索

  1. class Solution {
  2.     int[][] memo;
  3.     int[] v;
  4.     public int minScoreTriangulation(int[] v) {
  5.         this.v = v;
  6.         memo = new int[v.length][v.length];
  7.         for(int[] i : memo){
  8.             Arrays.fill(i,-1);
  9.         }
  10.         return dfs(0,v.length-1);
  11.     }
  12.     public int dfs(int i, int j){
  13.         if(i+1 == j) return 0;
  14.         if(memo[i][j] != -1) return memo[i][j];
  15.         int res = Integer.MAX_VALUE;
  16.         for(int k = i+1; k < j; k++){
  17.             res = Math.min(res,dfs(i,k)+dfs(k,j)+v[i]*v[j]*v[k]);
  18.         }
  19.         memo[i][j] = res;
  20.         return res;
  21.     }
  22. }

动态规划

  1. class Solution {
  2.     public int minScoreTriangulation(int[] v) {
  3.         int[][] dp = new int[v.length][v.length];
  4.         for(int i = v.length-3; i >= 0; i--){
  5.             for(int j = i+2; j < v.length; j++){
  6.                 dp[i][j] = Integer.MAX_VALUE;
  7.                 for(int k = i+1; k < j; k++){
  8.                     dp[i][j] = Math.min(dp[i][j],dp[i][k]+dp[k][j]+v[i]*v[j]*v[k]);
  9.                 }  
  10.             }
  11.         }
  12.         return dp[0][v.length-1];
  13.     }
  14. }

本方法小结： 

（1）dp[i][j]代表从i到j区间内所构成的三角形面积的最小值

（2）i从length-3开始可以理解成 从i开始最少需要三条边构成三角形，j和k都比i要大，所以从i-3开始满足能成立一个三角形，j从i+2开始是因为中间需要留至少一个k的空间，最后k在i和j中取值，左虚右虚

（3）由于k比i大，而 dp[i][j]需要dp[i][k]作为基础，所以i的转移方向为从大到小，同理，j的方向为从小到大

经典枚举区间

  1. class Solution {
  2.     public int minScoreTriangulation(int[] v) {
  3.         int n = v.length;
  4.         int[][] dp = new int[n][n];
  5.         for(int len = 3; len <= n; len++){
  6.             for(int L = 0; L+len-1 < n; L++){
  7.                 int R = L + len - 1;
  8.                 dp[L][R] = 0x3f3f3f3f;
  9.                 for(int k = L+1; k < R; k++){
  10.                     dp[L][R] = Math.min(dp[L][R], dp[L][k] + dp[k][R] + v[L]*v[R]*v[k]);
  11.                 }
  12.             }
  13.         }
  14.         return dp[0][n-1];
  15.     }
  16. }

本方法小结：

（1）以上的方法都是枚举左右端点，此方法为经典的枚举区间

（2）区间长度len最少从3开始，长度大于等于3才能构成三角形，枚举左端点，右端点为左端点加上区间长度，然后枚举中间的k点（相当于三角形的顶点）

（3）一般的区间DP都是枚举区间，然后枚举左右端点，这题可以直接枚举左右端点，然后枚举中间的k点

参考来源Ref.

[1] leetcode 灵茶山艾府 【视频讲解】教你一步步思考动态规划！（Python/Java/C++/Go）

[2] leetcode Chisato 【视频讲解】教你一步步思考动态规划！（Python/Java/C++/Go）

[3] leetcode  return up; C++：动态规划（新瓶装旧酒）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/531596
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号