[LeetCode]-动态规划-4

这篇具有很好参考价值的文章主要介绍了[LeetCode]-动态规划-4。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

记录 LeetCode 刷题时遇到的动态规划相关题目,第四篇

1504.统计全1子矩形

枚举算法:首先对整个矩阵生成一个 row 数组,其中 row[i][j] 表示从 mat[i][j] 开始往左连续的 1 的个数

然后枚举的思路是,枚举所有的 mat[i][j],求以 mat[i][j] 为右下角的子矩形 的个数,然后求和,具体的求法是枚举以 mat[i][j] 为右下角的子矩形的每个宽。这里以横向为矩形的长,纵向为矩形的宽。那么当宽为 1 的时候,子矩形的个数自然就是 row[i][j];当宽为 [2,i + 1],由于跨越了多行,矩形的长就应该取这些行中最短的长,即 当行坐标为 k 时,子矩形的长必须是 Math.min(row[p,j]),p∈[k,i],即取从第 k 行到第 i 行之间最短的长,才能保证子矩形是完整的

class Solution {
    public int numSubmat(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[][] row = new int[n][m];
        //生成row数组
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (j == 0) {
                    row[i][j] = mat[i][j];
                } else if (mat[i][j] != 0) {
                    row[i][j] = row[i][j - 1] + 1;
                } else {
                    row[i][j] = 0;
                }
            }
        }
        int ans = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                int minWidth = Integer.MAX_VALUE;
                //由于要取从k到i行之间最短的长,所以要倒序列举k                 
                for(int k = i;k >= 0;k--){
                    //当遇到第j列上某个格子不为1,则继续往上也得不到完整的矩形了
                    if(row[k][j] == 0){
                        break;
                    }
                    minWidth = Math.min(minWidth,row[k][j]);
                    ans += minWidth;
                }
            }
        }
        return ans;
    }
}

887. 鸡蛋掉落

参考题解
本题求的是已知鸡蛋个数 k 和楼层数 n,最坏情况下能锁定 f 的扔鸡蛋次数,反过来想,我们可以求有 t 个操作次数以及 k 个鸡蛋的情况下,能够确定 f 的最大层数 n

那么该问题中的状态就是 剩余的操作次数 t 以及剩余的鸡蛋数 k,我们令 dp[t][k] 等于该状态下的 n。即剩余操作次数为 t 以及剩余鸡蛋数为 k 的情况下 (能锁定 f 的) 最大层数为 n,对于这 n 层楼,我们随机选一层来扔鸡蛋,那么这 n 层的层数就会等于操作所处的这一层加上这一层上面的所有层的层数以及这一层下面的所有层的层数。

为了求这一层上面的所有层的层数,需要我们在这一层操作时鸡蛋没碎,因为只有鸡蛋没碎,说明 f 在上面的层中,我们才会向上面的层去继续操作。那么鸡蛋数不变,但操作数减一,对应的状态为 dp[t - 1][k]
同理,要求下面的所有层的层数,需要鸡蛋碎了,说明 f 在下面的层中,我们才会向下去寻找,对应的状态就是 dp[t - 1][k]。无论是向上还是向下寻找,机会数都应该减一
再加上操作的这一层,得到状态转移方程为 dp[t][k] = dp[t - 1][k - 1] + dp[t - 1][k] + 1

k 的边界,即鸡蛋总数,题目是给定的;而 t 操作次数没有给定,但可以看出来操作次数绝对不会超过楼层数,所以 t <= n

边界条件:当操作次数只有 1 次时,能确定的最高楼层只能为 1

根据状态转移方程,可以降维,这里直接使用一维数组的做法:

public int superEggDrop(int k, int n) {
    if(n == 1) return 1;
    int[] dp = new int[k + 1];
    for(int i = 1;i <= k;i++){
        dp[i] = 1;
    }
    for(int i = 2;i <= n;i++){
        for(int j = k;j >= 1;j--){
            dp[j] += dp[j - 1] + 1;
            if(dp[j] >= n) return i;
        }
    }
    return -1;
}

91. 解码方法

看完题意第一反应就是回溯,没看数据规模就直接是写一个回溯,写完跑了两个样例全对,直接自信提交,提前沉浸在一发就过的喜悦中,结果直接超时…

看了数据规模,100,打扰了。
不过看到评论区有人就是回溯然后剪枝过了,emmm,算了,最优解还得是动态规划:

对于一个字符串,如果最后一个字符能够解码,即是大于 0 的数,那么这个字符串的解码方法可以是最后一个字符前的字符串的解码方法再把最后一个字符单独解码;如果最后两个字符能够解码,即倒数第二个字符不为 0 而且最后两个字符对应的数小于等于 26,那么这个字符串的解码方法还可以是最后两个字符前的字符串的解码方法再把最后这两个字符一起解码。两种情况都满足的话可以叠加

dp[i] 表示 s 中长为 i 的子串 (子串开头都是 s[0]) 的解码方法数,边界为 dp[0] = 1,表示长为 0,即空串的解码方法为 1 种。

public int numDecodings(String s) {
    char[] cs = s.toCharArray();
    int[] dp = new int[cs.length + 1];
    dp[0] = 1;//边界
    for(int i = 1;i <= cs.length;i++){
    	//第一种情况
        if(cs[i - 1] != '0') dp[i] += dp[i - 1];
        //第二种情况
        if(i > 1 && cs[i - 2] != '0' && ((cs[i - 2] - '0') * 10 + (cs[i - 1] - '0') <= 26)) dp[i] += dp[i - 2];
    }
    return dp[cs.length];
}

279. 完全平方数

状态 dp[i] 表示和为 i 的完全平方数的最少数量。

i 由一系列完全平方数累加得到,这些完全平方数的根号一定在 [1,sqrt(i)] 的范围中,那么我们枚举范围中的每一个数 j,i 就可以等于 j2 + i - j2,如果我们知道和为 i - j2 的完全平方数的最少数量,即 dp[i - j2],不就知道这种情况下和为 i 的完全平方数的数量为 dp[i - j2] + 1 (1 指的是 j2)。枚举所有的 j 计算每种情况下对应的最少数量,取最少的一个就是和为 i 的完全平方数的最少数量 dp[i]。这也是状态的转移过程。

边界是 dp[0] = 0,表示和为 0 的完全平方数的最少数量为 0,没有任何完全平方数的和可以为 0。

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp,Integer.MAX_VALUE);
    dp[0] = 0;
    int sqrt;
    for(int i = 1;i <= n;i++){
        sqrt = (int)Math.sqrt(i);
        for(int j = 1;j <= sqrt;j++){
            dp[i] = Math.min(dp[i],1 + dp[i - j * j]);
        }
    }
    return dp[n];
}

10. 正则表达式匹配

每次匹配时,我们可以先考察两个表达式的右端是否匹配,如果右端不匹配,则两个表达式一定不匹配;而如果右端匹配,则我们需要继续往前判断左端是否匹配。可以看出来问题存在子结构的特点,也即动态规划的特点,因此可以考虑使用动态规划来解决问题

字符串与动态规划结合的题型中存在这样的规律:如果是对单个字符串进行 dp,则需要一个一维数组作为 dp 数组,其中 dp[0,i] 表示对原字符串 [0,i] 的区间上的子问题的解;如果是对两个字符串进行 dp,则

class Solution {
    public boolean isMatch(String s, String p) {
        char[] cs = s.toCharArray(),cp = p.toCharArray();
        boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];
        dp[0][0] = true;
        //如果p长度为0,s长度大于0,则一定不匹配,即dp[1...cs.length][0] = false
        //如果s长度为0,p长度大于0,则需要计算能否匹配
        for(int i = 1;i <= cp.length;i++){
            if(cp[i - 1] == '*'){
                dp[0][i] = dp[0][i - 2];
            }
        }
        for(int i = 1;i <= cs.length;i++){
            for(int j = 1;j <= cp.length;j++){
                if(cp[j - 1] == cs[i - 1] || cp[j - 1] == '.'){
                    dp[i][j] = dp[i - 1][j - 1];
                }else if(cp[j - 1] == '*'){
                    if(cp[j - 2] == cs[i - 1] || cp[j - 2] == '.'){
                        dp[i][j] = dp[i][j - 2] || 
                                    dp[i - 1][j];
                    }else{
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[cs.length][cp.length];
    }
}

120. 三角形最小路径和

自底向上进行动态规划推导,状态 dp[i][j] 表示第 i 行第 j 个位置处的最小路径和,那么状态转移方程为 dp[i][j] = min(dp[i + 1][j],dp[i + 1][j + 1]) + triangle[i][j],可以看到 dp 值只跟下一层的 dp 值有关,因此可以降为一维 dp,dp[i] = min(dp[i],dp[i + 1]), + triangle[i][j]
由于是自底向上,那么边界就是最底层的那条边

public int minimumTotal(List<List<Integer>> triangle) {
	// 把三角形每一行的第一个元素对齐,长跟宽就是等长的
    int lengthOrWidth = triangle.size();
    int[] dp = new int[lengthOrWidth];
    // 状态边界
    for(int i = 0;i < lengthOrWidth;i++){
        dp[i] = triangle.get(lengthOrWidth - 1).get(i);
    }
    // 状态推导
    for(int i = lengthOrWidth - 2;i >= 0;i--){
        for(int j = 0;j <= i;j++){
            dp[j] = Math.min(dp[j],dp[j + 1]) + triangle.get(i).get(j);
        }
    }
    return dp[0];
}

72. 编辑距离

状态定义:二维数组 dp,dp[i][j] (i >0 && j > 0) 表示 word1 中从第 1 到第 i 个字符段,要将其转换到和 word2 中从第 1 到第 j 个字符相同,所需的最少步数

边界

  1. 0 表示空串,即 dp[0][0] 表示 word1 空串部分要转换到和 word2 空串部分相同所需的最少步数,显然为 0
  2. dp[0][j] 表示 word1 空串部分要转换到和 word2 中从第 1 到第 j 个字符这段区间的字符相同所需的步数,显然只能在空串的基础上做添加操作,所以 dp[0][j] = j
  3. dp[i][0] 表示 word1 中从第 1 到第 i 个字符这段字符要转换到和 word2 中空串部分相同所需的步数,显然也一样只能做添加操作,所以 dp[i][0] = i

转移方程

  1. 如果 word1 中第 i 个字符跟 word2 中第 j 个字符恰好相同,那么就相当于在 dp[i - 1][j - 1] 的基础上两者分别加上了相同的第 i 跟第 j 个字符,所以要转换的步数与 dp[i - 1][j - 1] 相同;

  2. 如果 word1 第 i 个字符跟 word2 第 j 个字符不相同,那么

    • 可以在 dp[i - 1][j - 1] 的基础上将 word1 的第 i 个字符 替换 为 word2 的第 j 个字符,即 dp[i - 1][j - 1] + 1;
    • 也可以先让 word1 第 1 到第 i - 1 字符段跟 word2 的第 1 到第 j 字符段相同,然后再 删去 word1 第 i 个字符,即 dp[i - 1][j] + 1;
    • 还可以让 word1 第 1 到第 i 字符段跟 word2 第 1 到 j - 1 字符段相同,然后再在 word1 后面 增加 word2 的第 j 个字符,即 dp[i][j - 1] + 1。

    至于选择哪个方案就看哪个方案的总步数更少

例如示例1的 word1 = “horse”, word2 = “ros”,要求 dp[5][3],由于 word1 的第 5 个字符跟 word2 的第 3 个字符不相等,所以可以:先让 word1 中 “hors” 变为 “ro”,然后把 "e"变为 “s”,这就是替换,dp[4][2] + 1;也可以先让 “hors” 转换到 “ros”,然后删除掉最后的 “e”,dp[4][3] + 1;还可以先让 “horse” 转换到 “ro”,然后在最后加多一个 “s”,dp[5][2] + 1

PS:这道题发现将字符串转化为字符数组然后在后面状态转移中使用c2[i - 1] == c1[j - 1]来判断要比不转化为字符数组直接word1.charAt(i - 1) == word2.charAt(j - 1) 快了那么1ms文章来源地址https://www.toymoban.com/news/detail-819628.html

public int minDistance(String word1, String word2) {
    char[] c1 = word1.toCharArray();
    char[] c2 = word2.toCharArray();
    int[][] dp = new int[c1.length + 1][c2.length + 1];
    dp[0][0] = 0;
    for(int i = 1;i <= c1.length;i++){
        dp[i][0] = i;
    }
    for(int i = 1;i <= c2.length;i++){
        dp[0][i] = i;
    }
    for(int i = 1;i <= c1.length;i++){
        for(int j = 1;j <= c2.length;j++){
            if(c1[i - 1] == c2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            }else{
                //                      替换                      删除          插入
                dp[i][j] = Math.min(dp[i - 1][j - 1],Math.min(dp[i - 1][j],dp[i][j - 1])) + 1;
            }
        }
    }
    return dp[c1.length][c2.length];
}

到了这里,关于[LeetCode]-动态规划-4的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法|动态规划No.6】leetcode63. 不同路径Ⅱ

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月16日
    浏览(49)
  • 【算法|动态规划No.17】leetcode64. 最小路径和

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(49)
  • 【算法|动态规划系列No.5】leetcode62. 不同路径

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月12日
    浏览(43)
  • 【算法|动态规划No.12】leetcode152. 乘积最大子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(45)
  • 【算法|动态规划No.7】leetcode300. 最长递增子序列

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(46)
  • 【算法|动态规划No.15】leetcode1035. 不相交的线

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(44)
  • leetCode 131.分割回文串 + 动态规划 + 回溯算法 + 优化 + 图解 + 笔记

    我的往期文章: leetCode 647.回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501 leetCode 131.分割回文串 + 回溯算法 + 图解 + 笔记-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/134700907?spm=1001.2014.3001

    2024年02月05日
    浏览(56)
  • 【算法|动态规划No30】leetcode5. 最长回文子串

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(41)
  • 【手撕算法|动态规划系列No.4】leetcode91. 解码方法

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月12日
    浏览(41)
  • 【leetcode刷题之路】剑指Offer(4)——分治+排序算法+动态规划

    8 分治算法 8.1 【递归】剑指 Offer 07 - 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/   前序遍历是根左右,中序遍历是左根右,这也就意味着前序遍历的第一个节点是整棵树的根节点,顺着这个节点找到它在中序遍历中的位置,即为in_root,那么in_root左边的都在左子

    2024年02月11日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包