前言
1、多边形三角剖分的最低得分
2、猜数字大小 II
3、让字符串成为回文串的最少插入次数
4、切棍子的最小成本
5、戳气球
6、合并石头的最低成本
每日一题day76：多边形三角剖分的最低得分（力扣1039）
分析：
大佬详细题解
class Solution {
public int minScoreTriangulation(int[] values) {
int[][] dp = new int[values.length][values.length];
for(int i=values.length-3;i>=0;i--){ //注意 i从values.length-3开始
for(int j=i+2;j<values.length;j++){ //j从i+2开始
//i倒序枚举 j正序枚举
int res = Integer.MAX_VALUE;
for(int k = i+1;k<j;k++){
res = Math.min(res,dp[k][j]+dp[i][k]+values[i]*values[j]*values[k]);
}
dp[i][j] = res;
}
}
return dp[0][values.length-1];
}
}
每日一题类似题目：猜数字大小 II（力扣375）
分析：
这一段题解是灵魂！
大佬题解
类似于算法书中的矩阵连乘问题
class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n+1][n+1];
for(int i = n-1;i>=1;i--){
for(int j=i+1;j<=n;j++){
dp[i][j] = j+dp[i][j-1];
for(int k=i;k<j;k++){
dp[i][j] = Math.min(dp[i][j],Math.max(dp[i][k-1],dp[k+1][j])+k);
}
}
}
return dp[1][n];
}
}
每日一题类似题目：让字符串成为回文串的最少插入次数（力扣1312）
分析：
跟判断回文串思路一样，但是需要反过来处理
如果当前两个字符相等 s[i] == s[j] 那么就不需要做任何处理 dp[i][j] = dp[i+1][j-1]
反之，如果当前两个字符不相等，那么就需要增加操作数了，那么选择增加哪个字符 操作数最少？dp[i][j] = Math.min(dp[i+1][j],dp[i][j-1])+1;
class Solution {
public int minInsertions(String s) {
int n = s.length();
int[][] dp = new int[n+1][n+1];
for(int i=n-1;i>=1;i--){
for(int j=i+1;j<=n;j++){
if(s.charAt(i-1)!=s.charAt(j-1)){
dp[i][j] = Math.min(dp[i][j-1],dp[i+1][j])+1;
}else{
dp[i][j] = dp[i+1][j-1];
}
}
}
return dp[1][n];
}
}
每日一题类似题目：切棍子的最小成本（力扣1547）******hard
分析：
有些类似于矩阵连乘问题：
class Solution {
public int minCost(int n, int[] cuts) {
int length = cuts.length;
//数组扩容 加0 和n
Arrays.sort(cuts);
int[] newCuts = new int[length+2];
for(int i=0;i<length;i++){
newCuts[i+1] = cuts[i];
}
newCuts[0] = 0;
newCuts[length+1] = n;
int len = length+2;
int[][] dp = new int[len][len];
for(int i=len-3;i>=0;i--){
for(int j=i+2;j<len;j++){
int ans = Integer.MAX_VALUE;
for(int k = i+1;k<j;k++){
ans = Math.min(ans,dp[i][k]+dp[k][j]);
}
dp[i][j] = ans + newCuts[j]-newCuts[i];
}
}
return dp[0][len-1];
}
}
每日一题类似题目：戳气球（力扣312）******hard
分析：
类似于矩阵连乘问题：
class Solution {
public int maxCoins(int[] nums) {
int n =nums.length+2;
int[] newNums = new int[n];
for(int i=0;i<nums.length;i++){
newNums[i+1] = nums[i];
}
newNums[0] =1;
newNums[n-1] = 1;
int[][] dp = new int[n][n];
for(int i=n-3;i>=0;i++){
for(int j=i+2;j<n;j++){
int ans = 0;
for(int k=i+1;k<j;k++){
ans = Math.max(ans,dp[i][k]+dp[k][j]+newNums[i]*newNums[j]*newNums[k]);
}
dp[i][j] = ans;
}
}
return dp[0][n-1];
}
}
每日一题day78类似题目：合并石头的最低成本（力扣1000）**************So hard
文章来源：https://www.toymoban.com/news/detail-412140.html
分析：
大佬题解
比戳气球难理解多了文章来源地址https://www.toymoban.com/news/detail-412140.html
class Solution {
public int mergeStones(int[] stones, int k) {
int n = stones.length;
if((n-1)%(k-1)>0){
return -1;
}
//前缀和数组
int[] pre = new int[n+1];
int res = 0;
for(int i=0;i<stones.length;i++){
res +=stones[i];
pre[i+1]+=res;
}
int[][] dp = new int[n][n];
//开始合成石头
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++){
dp[i][j] = Integer.MAX_VALUE;
for(int m = i;m<j;m+=k-1){
dp[i][j] = Math.min(dp[i][j],dp[i][m]+dp[m+1][j]);
}
if((j-i)%(k-1)==0){
//合并为1堆
dp[i][j] += pre[j+1]-pre[i];
}
}
}
return dp[0][n-1];
}
}
到了这里，关于day78【代码随想录】区间DP专题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
