区间dp)/221. 最大正方形 / 1312. 让字符串成为回文串的最少插入次数(区间dp)"/>
(动态规划)1547. 切棍子的最小成本(区间dp)/221. 最大正方形 / 1312. 让字符串成为回文串的最少插入次数(区间dp)
1547. 切棍子的最小成本
题目描述
有一根长度为 n 个单位的木棍,棍上从 0 到 n 标记了若干位置。例如,长度为 6 的棍子可以标记如下:
给你一个整数数组 cuts ,其中 cuts[i] 表示你需要将棍子切开的位置。
你可以按顺序完成切割,也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度,切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍(这两根木棍的长度和就是切割前木棍的长度)。请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。
示例 1:
输入:n = 7, cuts = [1,3,4,5]
输出:16
解释:按 [1, 3, 4, 5] 的顺序切割的情况如下所示:
第一次切割长度为 7 的棍子,成本为 7 。第二次切割长度为 6 的棍子(即第一次切割得到的第二根棍子),第三次切割为长度 4 的棍子,最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后,总成本 = 16(如示例图中 7 + 4 + 3 + 2 = 16)。
示例 2:
输入:n = 9, cuts = [5,6,1,4,2]
输出:22
解释:如果按给定的顺序切割,则总成本为 25 。总成本 <= 25 的切割顺序很多,例如,[4, 6, 5, 2, 1] 的总成本 = 22,是所有可能方案中成本最小的。
提示:
2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
cuts 数组中的所有整数都 互不相同
来源:力扣(LeetCode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
区间dp,学习
class Solution {public int minCost(int n, int[] cuts) {//区间dp//dp[i][j]表示表示在当前待切割的木棍的左端点为cuts[i],右端点为cuts[j] 时,将木棍全部切开的最小总成本。//那么怎么更新呢,//首先在左右两端各加一个切割点,0和n//在dp[i][j]内共有cut[i + 1],cut[i + 2]...cut[j - 1]个切割点,枚举这些切割点,可以将木棍分成更小的部分//dp[i][j] = dp[i][k] + dp[k][j] + len;//也就是子问题int m = cuts.length;//对cuts数组排序,即对切割点进行排序Arrays.sort(cuts);//加开头和结尾两个点,复制到新的数组中int[] cutss = new int[m + 2];cutss[0] = 0;cutss[m + 1] = n;System.arraycopy(cuts, 0, cutss, 1, m);int[][] dp = new int[m + 2][m + 2];//相邻两个点切割成本为0dp[0][0] = 0;for(int i = 1; i < m + 2; i++){dp[i][i] = 0;dp[i - 1][i] = 0;}//因为根据更新规则,i依赖于比它大的,j依赖于比它小的,所以i从大大小遍历,j从小到大for(int i = m; i >= 0; i--){for(int j = i + 2; j < m + 2; j++){//如果i和j相等,那么只有一个切割点,dp[i][j] = Integer.MAX_VALUE;//遍历所有的分割点for(int k = i + 1; k < j; k++){dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);}dp[i][j] += cutss[j] - cutss[i];}}return dp[0][m + 1];}
}
221. 最大正方形
题目描述
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内,找到只包含 ‘1’ 的最大正方形,并返回其面积。
示例 1:
输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出:4
示例 2:
输入:matrix = [[“0”,“1”],[“1”,“0”]]
输出:1
示例 3:
输入:matrix = [[“0”]]
输出:0
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’
来源:力扣(LeetCode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
只能想到用前缀和处理面积,然后遍历开始位置和正方形边长,根据前缀和处理面积是否等于边长的平方
怎么动态规划呢?
class Solution {public int maximalSquare(char[][] matrix) {//我能想到的就是矩阵的前缀和,然后遍历开始位置和正方形的边长大小,确定一个最大的正方形//就和牛客模拟笔试那个题一样//怎么动态规划呢//dp[i][j]表示以(i,j)为右下角,最大的正方形边长//此时,和dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]有关系,//就等于三者的最小值,加1//因为如果想要扩展这个正方形的边长,那么这三个值,肯定都得是一样的,否则,只能由最小的来表示当前的正方形int m = matrix.length;int n = matrix[0].length;int[][] dp = new int[m + 1][n + 1];int max = 0;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(matrix[i - 1][j - 1] == '0'){dp[i][j] = 0;continue;}dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;max = Math.max(max, dp[i][j]);}}return max * max;}
}
1312. 让字符串成为回文串的最少插入次数
这周力扣推荐的题
题目描述
给你一个字符串 s ,每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1:
输入:s = “zzazz”
输出:0
解释:字符串 “zzazz” 已经是回文串了,所以不需要做任何插入操作。
示例 2:
输入:s = “mbadm”
输出:2
解释:字符串可变为 “mbdadbm” 或者 “mdbabdm” 。
示例 3:
输入:s = “leetcode”
输出:5
解释:插入 5 个字符后字符串变为 “leetcodocteel” 。
示例 4:
输入:s = “g”
输出:0
示例 5:
输入:s = “no”
输出:1
提示:
1 <= s.length <= 500
s 中所有字符都是小写字母。
来源:力扣(LeetCode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
一眼望去就是动规
class Solution {public int minInsertions(String s) {//dp[i][j]表示i到j成为回文串的最小操作次数//如果s[i]和s[j]相同,那么就是dp[i + 1][j - 1]//如果不同,那么就需要添加一个字符,可以添加在开头,也可以添加在结尾,即考虑dp[i + 1][j](添加在了末尾)//或者dp[i][j - 1](添加在了开头)int l = s.length();int[][] dp = new int[l][l];//i依赖于i+1,j依赖于j-1for(int i = l - 2; i >= 0; i--){for(int j = i + 1; j < l; j++){if(s.charAt(i) == s.charAt(j))dp[i][j] = dp[i + 1][j - 1];else{dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i + 1][j] + 1);}}}return dp[0][l - 1];}
}
或者还可以这样想,也就是官解1的做法:
题目表示求让一个字符串变为回文串的最少插入操作,意思就是这个字符串里面最长的回文子序列的长度是多少,其他字符要形成回文需要对称的添加;所以用字符串长度减去最长回文子序列即可
这个不太好理解
更多推荐
(动态规划)1547. 切棍子的最小成本(区间dp)/221. 最大正方形 / 1312. 让字符串成为回文串的最少插入次数(区间dp)
发布评论