前言

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 和nArrays.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

分析：
大佬题解
比戳气球难理解多了

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];}
}