动态规划2

目录

121 买卖股票的最佳时机

打家劫舍

62 不同路径

64 最小路径和

53 最大子数组和 （动归 普通数组部分）

152 乘积最大子数组

300 最长递增子序列

1143 最长公共子序列

72 编辑距离

121 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int[][] dp = new int[len][2];
        //第一天持有股票，只能是第一天购入，收益为-prices
        dp[0][0] = -prices[0];
        //第一天不持有股票，既没有购买，收益为0
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            //第i天持有，可能是前一天购入，或当天购入
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            //第i天不持有，可能是前一天持有，今天售出或前一天也不持有(保持现状)
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        //本题中不持有股票状态所得金钱一定比持有股票状态得到的多！
        return dp[len - 1][1];
    }
}

打家劫舍

如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

class Solution {
    public int rob(int[] nums) {
        // 考虑下标 i（包括 i）以内的房屋，最多可以偷窃的金额为 dp[i]。
        // 如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] 因为求的是能偷的最高金额，因此尽量不走空
        // 如果不偷第i房间，那么dp[i] = dp[i - 1] (只是考虑偷i-1不一定真的偷)
        // 然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        // dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值
        if (nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1]; //数组下标从0开始
    }

}

62 不同路径

一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
        // dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        // dp[i][0],dp[0,j]一定都是1
        int[][] dp = new int[m][n];
        // 初始化
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

64 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

不使用备忘录计数，更好理解

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        // 初始化第一行
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        // 初始化第一列
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        // 填充剩余格子
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
}

53 最大子数组和 （动归 普通数组部分）

子数组是数组中的一个连续部分。

动规解法

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        // base case
        // 第一个元素前面没有子数组
        dp[0] = nums[0];
        // 状态转移方程
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }
        // 得到 nums 的最大子数组
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

152 乘积最大子数组

dp 数组是：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」，从而写出状态转移方程。

这道题和 上一题的最大区别在于，要同时维护「以 nums[i] 结尾的最大子数组」和「以 nums[i] 结尾的最小子数组」，以便适配 nums[i] 可能为负的情况。

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;

        // 定义：以 nums[i] 结尾的子数组，乘积最小为 dp1[i]
        int[] dp1 = new int[n];
        // 定义：以 nums[i] 结尾的子数组，乘积最大为 dp2[i]
        int[] dp2 = new int[n];

        // base case
        dp1[0] = nums[0];
        dp2[0] = nums[0];

        // 状态转移方程  需要和 nums[i]比较 以nums[i]为结尾的数组
        //单独的 nums[i] 可能作为一个新的子数组。
        for (int i = 1; i < n; i++) {
            dp1[i] = min(dp1[i - 1] * nums[i], dp2[i - 1] * nums[i], nums[i]);
            dp2[i] = max(dp1[i - 1] * nums[i], dp2[i - 1] * nums[i], nums[i]); 
        }

        // 遍历所有子数组的最大乘积，求最大值
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp2[i]);
        }

        return res;
    }

    int min(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    int max(int a, int b, int c) {
        return Math.max(Math.max(a, b), c);
    }
}

300 最长递增子序列

子数组一定是连续的，而子序列不一定是连续的。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

dp 数组的定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

那么 dp 数组中最大的那个值就是最长的递增子序列长度。

子数组一定是连续的，而子序列不一定是连续的。
class Solution {
    public int lengthOfLIS(int[] nums) {
        // dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];

        // base case：dp 数组全都初始化为 1
        Arrays.fill(dp, 1);
         //快慢指针
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

1143 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

  • dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
  • 两种情况：text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
    • 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以 dp[i][j] = dp[i - 1][j - 1] + 1;
    • 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    • dp 数组的第0行和第0列用于表示空字符串的情况
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {  
        //dp 数组的第0行和第0列用于表示空字符串的情况
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                char char1 = text1.charAt(i - 1);  
                //当 dp 数组的索引为 i 和 j 时，我们实际上是在处理 text1 的第 i-1 个字符和 text2 的第 j-1 个字符
                char char2 = text2.charAt(j - 1);
                if (char1 == char2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

72 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

  1. if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];
  2. if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？
  • 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。

即 dp[i][j] = dp[i - 1][j] + 1;

  • 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。

即 dp[i][j] = dp[i][j - 1] + 1;

  • 操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增删加元素。

可以回顾一下，if (word1[i - 1] == word2[j - 1])的时候我们的操作 是 dp[i][j] = dp[i - 1][j - 1] 对吧。

那么只需要一次替换的操作，就可以让 word1[i - 1] 和 word2[j - 1] 相同。

所以 dp[i][j] = dp[i - 1][j - 1] + 1;

class Solution {
    public int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        // base case 有一个里面没元素
        for (int i = 1; i <= m; i++) //对word1里的元素全部做删除操作
            dp[i][0] = i;
        for (int j = 1; j <= n; j++)
            dp[0][j] = j;
        // 自底向上求解
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
             // 因为dp数组有效位从1开始
             // 所以当前遍历到的字符串的位置为i-1 | j-1
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(
                        dp[i - 1][j] + 1,//word1删除
                        dp[i][j - 1] + 1,//word2删除
                        dp[i - 1][j - 1] + 1//替换
                    );
        // 储存着整个 s1 和 s2 的最小编辑距离
        return dp[m][n];
    }

    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/746812.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

游戏AI的创造思路-技术基础-sigmoid函数详解

游戏AI的创造思路-技术基础-sigmoid函数详解

在前面的机器学习和深度学习的内容中&#xff0c;大量出现了sigmoid函数&#xff0c;所以本篇为大家介绍下sigmoid函数&#xff0c;希望对大家理解前面的算法和后面的Transformer有所帮助 目录 3.8. sigmoid函数 3.8.1. 定义 3.8.2. 性质 3.8.3. 应用 3.8.4. 缺点 3.8.5.…
阅读更多...
php，python AES/CBC/PKCS7Padding加密解密 base64/hex编码

php，python AES/CBC/PKCS7Padding加密解密 base64/hex编码

1. python版本 import base64 from Crypto.Cipher import AES from Crypto.Util.Padding import pad, unpadclass AESUtilCBC:def __init__(self, key, iv):self.key key.encode(utf-8)self.iv iv.encode(utf-8)self.pad_length AES.block_sizedef encrypt(self, data):try…
阅读更多...
JVM专题十一：JVM 中的收集器一

JVM专题十一：JVM 中的收集器一

上一篇JVM专题十&#xff1a;JVM中的垃圾回收机制专题中&#xff0c;我们主要介绍了Java的垃圾机制&#xff0c;包括垃圾回收基本概念&#xff0c;重点介绍了垃圾回收机制中自动内存管理与垃圾收集算法。如果说收集算法是内存回收的方法论&#xff0c;那么垃圾收集器就是内存回…
阅读更多...
Python代码打包成exe应用

Python代码打包成exe应用

目录 一、前期准备 二、Pyinstaller打包步骤 Pyinstaller参数详解 三、测试 Spec 文件相关命令 一、前期准备 &#xff08;1&#xff09;首先&#xff0c;我们需要确保你的代码可以在本地电脑上的pycharm正常运行成功。 &#xff08;2&#xff09;我们要先安装Pyinstalle…
阅读更多...
Epic登录转圈/Epic登录不上一直转圈的五种办法分享

Epic登录转圈/Epic登录不上一直转圈的五种办法分享

Epic Games&#xff08;Epic商店&#xff09;是Epic旗下的数字游戏综合平台&#xff0c;不仅游戏数量众多&#xff0c;还可以每周在上面免费领取各种类型的热门游戏&#xff0c;深受国内游戏玩家追捧。不少玩家反馈在登录epic账号时会遇到转圈圈的情况&#xff0c;一直无法登录…
阅读更多...
cs与msf权限传递，与mimikatz抓取win2012明文密码

cs与msf权限传递，与mimikatz抓取win2012明文密码

CS与MSF的权限互相传递抓取windows2012的明文密码 CS与MSF的权限互相传递 1、启动cs服务端 2、客户端连接 3、配置监听&#xff0c;并设置监听端口为9999 4、生成脚本 5、开启服务&#xff0c;下载并运行木马 已获取权限 6、进入msf并设置监听 7、cs新建监听&#xff0c;与m…
阅读更多...
python-docx 设置页面边距、页眉页脚高度

python-docx 设置页面边距、页眉页脚高度

本文目录 前言一、docx 页面边距在哪里二、对 <w:pgMar> 的详细说明1、上边距的说明2、右边距的说明3、下边距的说明4、左边距的说明5、页眉高度的说明6、页脚高度的说明三、设置 docx 页边距、页眉页脚高度1、完整代码2、代码执行效果图四、补充一些内容1、页面边距的两…
阅读更多...
`THREE.PointsMaterial` 是 Three.js 中用于创建粒子系统材质的类。它允许你设置粒子系统的外观属性，比如颜色、大小和透明度。

`THREE.PointsMaterial` 是 Three.js 中用于创建粒子系统材质的类。它允许你设置粒子系统的外观属性，比如颜色、大小和透明度。

demo案例 THREE.PointsMaterial 是 Three.js 中用于创建粒子系统材质的类。它允许你设置粒子系统的外观属性&#xff0c;比如颜色、大小和透明度。下面是对其构造函数的参数、属性和方法的详细讲解。 构造函数 const material new THREE.PointsMaterial(parameters);参数&am…
阅读更多...
浏览器扩展V3开发系列之 chrome.commands 快捷键的用法和案例

浏览器扩展V3开发系列之 chrome.commands 快捷键的用法和案例

【作者主页】&#xff1a;小鱼神1024 【擅长领域】&#xff1a;JS逆向、小程序逆向、AST还原、验证码突防、Python开发、浏览器插件开发、React前端开发、NestJS后端开发等等 chrome.commands API 允许开发者使用快捷键来执行特定的命令。 在使用 chrome.commands API 之前必须…
阅读更多...
C# 入门—实现 Hello, World!

C# 入门—实现 Hello, World!

目录 一、.net 平台 二、.net 都能干什么&#xff1f; 三、.net 两种交互模式 四、使用 VS Code 开发 C# 程序 五、实现 Hello, World! 一、.net 平台 下载 .NET(Linux、macOS 和 Windows) (microsoft.com) .NET 简介 - .NET | Microsoft Learn C# :一种编程语言,可以开…
阅读更多...
文件管理—linux（基础IO）

文件管理—linux（基础IO）

目录 ​编辑 一、C语言文件接口&#xff08;库函数&#xff09; hello.c写文件 hello.c读文件 输出信息到显示器 stdin & stdout & stderr 二、系统文件I/O&#xff08;系统调用&#xff09; hello.c 写文件&#xff1a; hello.c读文件 接口介绍 open open…
阅读更多...
MQTT服务器/MQTT_C#客户端/Websoket连MQTT

MQTT服务器/MQTT_C#客户端/Websoket连MQTT

MQTT(消息队列遥测传输)是ISO 标准(ISO/IEC PRF 20922)下基于发布/订阅范式的消息协议。它工作在 TCP/IP协议族上，是为硬件性能低下的远程设备以及网络状况糟糕的情况下而设计的发布/订阅型消息协议，为此，它需要一个消息中间件 。 MQTT是一个基于客户端-服务器的消息发布/订…
阅读更多...
ue 材质贴图Tiling repeat

ue 材质贴图Tiling repeat

材质问题&#xff0c;如下 贴图显然不符合逻辑&#xff0c;太大&#xff0c;并且是一次性贴图 换一个红砖纹理&#xff0c;就看清了&#xff0c;砖太大了 修改&#xff1a; 拖出一个TexCoord&#xff0c;代表坐标&#xff0c;拖出一个参数&#xff0c;代表次数&#xff0c;如…
阅读更多...
Python数据分析之-Oracle数据库连接

Python数据分析之-Oracle数据库连接

文章目录 cx_Oracle 介绍cx_Oracle运行原理cx_Oracle 安装linux环境安装windows环境安装 cx_Oracle 使用单独使用结合Pandas使用 参考资料 cx_Oracle 介绍 cx_Oracle 8是一个Python扩展模块&#xff0c;它提供了对Oracle数据库的访问能力。以下是cx_Oracle 8的一些关键特性和功…
阅读更多...
【学习笔记】Hive

【学习笔记】Hive

Hive 作为数仓应用工具&#xff0c;对比 RDBMS&#xff08;关系型数据库&#xff09; 有3个“不能”&#xff1a; 不能像 RDBMS 一般实时响应&#xff0c;Hive 查询延时大&#xff1b; 不能像 RDBMS 做事务型查询&#xff0c;Hive 没有事务机制&#xff1b; 不能像 RDBMS 做行…
阅读更多...
Android性能优化——卡顿优化

Android性能优化——卡顿优化

文章目录 一、从XML到屏幕上的展示造成跳帧的因素有那些发现问题定位问题定位代码 一、从XML到屏幕上的展示 数据加载阶段 数据控制阶段 数据展示阶段 xml —> view onCreat —> 解析layout.xml resume —> view —> wms ViewRootImpl UI 绘制流程 &#xff1a;测…
阅读更多...
A股探底回升，跑出惊天大阳，你们知道为什么吗？

A股探底回升，跑出惊天大阳，你们知道为什么吗？

今天的A股&#xff0c;探底回升&#xff0c;让人惊呆了&#xff0c;你们知道是为什么吗&#xff1f;盘面上出现3个重要信号&#xff0c;一起来看看&#xff1a; 1、今天A股市场炸锅了&#xff0c;AI人工智能、国产软件、存储芯片迎来了涨停潮&#xff0c;惊呆了&#xff0c;科技…
阅读更多...
DataGrip 2024 mac/win版：让数据库管理更简单

DataGrip 2024 mac/win版：让数据库管理更简单

JetBrains DataGrip 2024 是一款专为数据库开发者设计的集成开发环境(IDE)&#xff0c;它凭借其卓越的性能和丰富的功能&#xff0c;为数据库管理提供了前所未有的便利。 DataGrip 2024 mac/win版获取 DataGrip 2024 支持几乎所有主流的关系型数据库管理系统&#xff0c;如 My…
阅读更多...
Vue41 ref属性

Vue41 ref属性

ref属性 ref是Vue提供的获取组件的属性 <template><div><h1 v-text"msg" ref"title"></h1><button ref"btn" click"showDOM">点我输出上方的DOM元素</button><MySchool ref"sch"…
阅读更多...
酷开科技丨酷开系统大屏购物 打造沉浸式购物体验

酷开科技丨酷开系统大屏购物 打造沉浸式购物体验

在这个信息化的时代&#xff0c;购物已经不仅仅局限于传统的线下店铺&#xff0c;线上购物逐渐成为了我们生活中重要的一部分。而大屏购物作为线上购物的一种形式&#xff0c;更是凭借其独特的优势和实用的技巧&#xff0c;成为了消费者们的新宠。随着科技的进步和消费者需求的…
阅读更多...
最新文章

Copyright @ 2022~2023