codetop标签动态规划大全C++讲解(三)！！动态规划刷穿地心！！学吐了家人们o(╥﹏╥)o

每天复习一篇，只有十题左右

  • 1.买卖股票的最佳时机
  • 2.买卖股票的最佳时机含手续费
  • 3.买卖股票的最佳时机III
  • 4.买卖股票的最佳时机IV
  • 5.打家劫舍
  • 6.打家劫舍II
  • 7.不同路径
  • 8.不同路径II
  • 9.最小路径和
  • 10.三角形的最小路径和
  • 11.两个字符串的删除操作
  • 12.编辑距离
  • 13.一和零

1.买卖股票的最佳时机

给prices数组，只能买卖一次！
0持有，1不持有
注意：只能买一次，状态不能从dp[i-1][1]转移，所以只有-prices[i]，如果不限次数就可以写dp[i - 1][1] - prices[i]了!!!

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(2, 0));dp[0][0] = -prices[0];for(int i = 1; i < prices.size(); i ++){dp[i][0] = max(- prices[i], dp[i - 1][0]);dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1]);}return dp[prices.size() - 1][1];}
};

2.买卖股票的最佳时机含手续费

无限次买卖，卖出同时需要付一笔手续费

因为是无限次买卖，所以状态从dp[i-1][1]转移，不限次数写成dp[i - 1][1] - prices[i]
买的时候减去fee

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {vector<vector<int>> dp(prices.size(), vector<int>(2, 0));//0持有,1不持有dp[0][0] = -prices[0];for(int i = 1; i < prices.size(); i ++){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);}return dp[prices.size() - 1][1];}
};

3.买卖股票的最佳时机III

限制最多可以完成两笔交易

class Solution {
public:int maxProfit(vector<int>& prices) {//0第一次持有,1第一次不持有,2第二次持有,3第二次不持有vector<vector<int>> dp(prices.size(), vector<int>(4, 0));dp[0][0] = -prices[0];dp[0][2] = -prices[0];for(int i = 1; i < prices.size(); i ++){dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);}return dp[prices.size() - 1][3];}
};

4.买卖股票的最佳时机IV

最多可以完成k笔交易，也就是说，最多可以买k次，卖k次

k从1开始，分奇偶

class Solution {
public:int maxProfit(int k, vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(2*k + 1, 0));//奇数持有，偶数不持有for(int i = 1; i < 2*k + 1; i ++){if(i % 2 == 1) dp[0][i] = -prices[0];}for(int i = 1; i < prices.size(); i ++){for(int j = 1; j <= 2*k - 1; j += 2){dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);}}return dp[prices.size() - 1][2 * k];}
};

5.打家劫舍

给定一个代表每个房屋存放金额的非负整数数组，相邻房屋装有相互连通的防盗系统，求最多偷的金额。
关键函数： dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);

class Solution {
public:int rob(vector<int>& nums) {vector<int> dp(nums.size(), 0);if(nums.size() == 0) return 0;if(nums.size() == 1) return nums[0];if(nums.size() == 2) return max(nums[0], nums[1]);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for(int i = 2; i < nums.size(); i ++){dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.size() - 1];}
};

6.打家劫舍II

房屋围城一圈，最后一个房屋和第一个房屋紧邻，偷相邻房间会自动报警

  1. 考虑不包含首尾元素
  2. 考虑包含首元素不包含尾元素
  3. 考虑不包含首元素包含尾元素
    考虑是包含但不一定要选，所以情况23包含了1
    简单点来说，考虑偷第一个不偷第二个和偷第二个不偷第一个的情况
    两个情况取最值，单领一个情况的计算就和I一样
class Solution {
public:int rob(vector<int>& nums) {int len = nums.size();if(len == 0) return 0;if(len == 1) return nums[0];if(len == 2) return max(nums[0], nums[1]);int result1 = robRange(nums, 0, len - 2);int result2 = robRange(nums, 1, len - 1);int result = max(result1, result2);return result;}int robRange(vector<int>& nums, int start, int end){vector<int> dp(nums.size() + 1, 0);dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for(int i = start + 2; i <= end; i ++){dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[end];}
};

7.不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
关键代码：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));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];}
};

8.不同路径II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for(int i = 0; i < m && obstacleGrid[i][0] == 0; i ++) dp[i][0] = 1;for(int j = 0; j < n && obstacleGrid[0][j] == 0; j ++) dp[0][j] = 1;for(int i = 1; i < m; i ++){for(int j = 1; j < n; j ++){if(obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};

9.最小路径和

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

注意边界问题，第一行第一列需要初始化，所有for都是从1开始的

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();vector<vector<int>> dp(m, vector<int>(n, 0));dp[0][0] = grid[0][0];for(int i = 1; i < m; i ++) dp[i][0] = dp[i - 1][0] + grid[i][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 ++){for(int j = 1; j < n; j ++){dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}return dp[m - 1][n - 1];}
};

10.三角形的最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
在这里插入图片描述
题目的意思，在相邻节点的条件下，求最小路径，与(i, j)点相邻的结点为(i + 1, j)和 (i + 1, j + 1)

第 i 行的第 j 个元素从哪里来？可以从第 i - 1 行第 j 或第 j - 1 个元素下落过来。
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]

注意边界！！！dp[i][0]必须初始化，dp[0][i]不用，因为dp[0][i]一定只有一个，毕竟三个三角形

class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {int m = triangle.size();vector<vector<int>> dp(m, vector<int>(m, INT_MAX));dp[0][0] = triangle[0][0];for(int i = 1; i < m; i ++) dp[i][0] = dp[i - 1][0] + triangle[i][0];for(int i = 1; i < m; i ++){for(int j = 1; j < triangle[i].size(); j ++){dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];}}int res = INT_MAX;for(int i = 0; i < m; i ++){res = min(res, dp[m - 1][i]);}return res;}
};

11.两个字符串的删除操作

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

dp[i][j]：以i-1为结尾的字符串word1，和以j-1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

  1. 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1]
  2. 当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
  • 删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
  • 删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
  • 删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
class Solution {
public:int minDistance(string word1, string word2) {int len1 = word1.size();int len2 = word2.size();vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));for(int i = 0; i <= len1; i ++) dp[i][0] = i;for(int i = 0; i <= len2; i ++) dp[0][i] = i;for(int i = 1; i <= len1; i ++){for(int j = 1; j <= len2; j ++){if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] =  min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));}}return dp[len1][len2];}
};

12.编辑距离

可以对一个单词进行增加，删除和替换，现有两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

dp[i][j]表示以下标i-1结尾的字符串word1，和以下标j-1结尾的字符串word2，最近编辑距离为dp[i][j]，所以i，j最大都可以达到len

  1. word[i - 1] == word2[j - 1]的时候不操作，dp[i][j]=dp[i-1][j-1]
  2. word1[i - 1] ！= word2[j - 1]的时候操作，分三种情况，增删换
  • 增加/删除：word1增加一个元素，相当于word2减少一个元素。比如word1 = “a”，word2 = “ab”，word1增加一个元素b和word2删除一个元素b的操作数是一样的；word1减少一个元素，相当于word2增加一个元素，比如word1 = “ab”，word2 = “a”，word1减少一个b和word2增加一个b用的操作数是一样的。所以dp[i][j] = dp[i][j - 1] + 1
  • 替换：dp[i][j] = dp[i - 1][j - 1] + 1
class Solution {
public:int minDistance(string word1, string word2) {int len1 = word1.size();int len2 = word2.size();vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));for(int i = 0; i <= len1; i ++) dp[i][0] = i;for(int i = 0; i <= len2; i ++) dp[0][i] = i;for(int i = 1; i <= len1; i ++){for(int j = 1; j <= len2; j ++){if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));}}return dp[len1][len2];}
};

13.一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

背包有2个维度，m个0和n个1属于背包，strs数组是物品，由于物品只能选一次，所以这是个01背包问题
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i] [j]。
递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for(string str : strs){//遍历物品int zoreNums = 0;int oneNums = 0;for(int i = 0; i < str.size(); i ++){if(str[i] == '0') zoreNums ++;else oneNums ++;}for(int j1 = m; j1 >= zoreNums; j1 --){//遍历背包，两个维度for(int j2 = n; j2 >= oneNums; j2 --){dp[j1][j2] = max(dp[j1][j2], dp[j1 - zoreNums][j2 - oneNums] + 1);}}}return dp[m][n];}
};

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

强化学习笔记之【DDPG算法】

强化学习笔记之【DDPG算法】

强化学习笔记之【DDPG算法】 文章目录 强化学习笔记之【DDPG算法】前言&#xff1a;原论文伪代码DDPG算法DDPG 中的四个网络代码核心更新公式 前言&#xff1a; 本文为强化学习笔记第二篇&#xff0c;第一篇讲的是Q-learning和DQN 就是因为DDPG引入了Actor-Critic模型&#x…
阅读更多...
Ubuntu22.04 Docker 国内安装最靠谱教程

Ubuntu22.04 Docker 国内安装最靠谱教程

目前docker在国内安装常存在众所周知的网络问题&#xff0c;如果安装过程如果从官网地址安装以及安装之后从官网要拉取镜像都存在问题。这篇文章主要针对这两个问题总结最靠谱的docker安装教程。 1. docker安装 1.1 系统环境概述 Ubuntu 22.04linux内核版本 6.8&#xff08;…
阅读更多...
重学SpringBoot3-集成Redis（四）之Redisson

重学SpringBoot3-集成Redis（四）之Redisson

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-集成Redis&#xff08;四&#xff09;之Redisson 1. 添加 Redisson 依赖2. 配置 Redisson 客户端3. 使用 Redisson 实现分布式锁4. 调用分布式锁5. 为什…
阅读更多...
二进制的神奇操作——拆位法和贡献思想

二进制的神奇操作——拆位法和贡献思想

拆位的引入 我们来思考这么一个问题&#xff0c;如果给你一个数组&#xff0c;让你去求一个数组里面所有连续子串的异或和的和&#xff0c;问你该怎么求&#xff1f; 我们该如何去处理&#xff0c;首先肯定是会想到暴力的思路&#xff0c;第一层循环遍历左端点&#xff0c;第…
阅读更多...
SpringBoot在线教育平台：设计与实现的深度解析

SpringBoot在线教育平台：设计与实现的深度解析

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…
阅读更多...
654、最大二叉树

654、最大二叉树

1、题目描述 . - 力扣&#xff08;LeetCode&#xff09; 其实就是给定了一个所谓"最大二叉树"的规则&#xff0c;让我们去构建二叉树。 以 nums [3,2,1,6,0,5] 为例&#xff0c;规则如下&#xff1a; (1)找出其中的最大值6将其作为根节点&#xff0c;6前面的是左子…
阅读更多...
程序传入单片机的过程，以Avrdude为例分析

程序传入单片机的过程，以Avrdude为例分析

在市场上有各式各样的单片机&#xff0c;例如Arduino&#xff0c;51单片机&#xff0c;STM等。通常&#xff0c;我们都用其对应的IDE软件进行单片机的编程。这些软件既负责将程序代码转写成二进制代码&#xff0c;即机器语言&#xff0c;也负责将该二进制代码导入单片机。与此同…
阅读更多...
C++ 算法学习——7.4.1 优化算法——双指针

C++ 算法学习——7.4.1 优化算法——双指针

双指针法&#xff08;Two Pointers&#xff09;是一种常用的算法技巧&#xff0c;通常用于解决数组或链表中的问题。这种技巧通过维护两个指针&#xff0c;通常分别指向数组或链表的不同位置&#xff0c;来协同解决问题。双指针法一般有两种类型&#xff1a;快慢指针和左右指针…
阅读更多...
什么是transformer大模型，答案就在这里

什么是transformer大模型，答案就在这里

Transformer大模型是一种在自然语言处理&#xff08;NLP&#xff09;领域中广泛使用的模型&#xff0c;其详细数据与分析可以从以下几个方面进行阐述&#xff1a; 1. 模型架构 Transformer模型本质上是一个Encoder-Decoder架构。编码组件由多层编码器&#xff08;Encoder&…
阅读更多...
（笔记）第三期书生·浦语大模型实战营（十一卷王场）–书生基础岛第3关---浦语提示词工程实践

（笔记）第三期书生·浦语大模型实战营（十一卷王场）–书生基础岛第3关---浦语提示词工程实践

学员闯关手册&#xff1a;https://aicarrier.feishu.cn/wiki/ZcgkwqteZi9s4ZkYr0Gcayg1n1g?open_in_browsertrue 课程视频&#xff1a;https://www.bilibili.com/video/BV1cU411S7iV/ 课程文档&#xff1a; https://github.com/InternLM/Tutorial/tree/camp3/docs/L1/Prompt 关…
阅读更多...
还在“卷”长度？长文本模型真的基于上下文进行回复吗？

还在“卷”长度？长文本模型真的基于上下文进行回复吗？

近年来&#xff0c;随着长文本模型&#xff08;Long-context Model, LCM&#xff09;技术的突飞猛进&#xff0c;处理长上下文的能力已成为各大语言模型&#xff08;Large Language Model, LLM&#xff09;的核心竞争力&#xff0c;也是各大技术厂商争夺的焦点。截至2023年12月…
阅读更多...
RAG再总结之如何使大模型更好使用外部数据：四个不同层级及查询-文档对齐策略

RAG再总结之如何使大模型更好使用外部数据：四个不同层级及查询-文档对齐策略

我们来看看RAG进展。《Retrieval Augmented Generation (RAG) and Beyond: A Comprehensive Survey on How to Make your LLMs use External Data More Wisely》(https://arxiv.org/abs/2409.14924)&#xff0c;主要讨论了如何使大型语言模型&#xff08;LLMs&#xff09;更明智…
阅读更多...
Redis中BitMap实现签到与统计连续签到功能

Redis中BitMap实现签到与统计连续签到功能

服务层代码 //签到Overridepublic Result sign() {//1.获取当前登录的用户Long userId UserHolder.getUser().getId();//获取日期LocalDateTime now LocalDateTime.now();//拼接keyString keySuffix now.format(DateTimeFormatter.ofPattern(":yyyyMM"));String …
阅读更多...
实例分割、语义分割和 SAM（Segment Anything Model）

实例分割、语义分割和 SAM（Segment Anything Model）

实例分割、语义分割和 SAM&#xff08;Segment Anything Model&#xff09; 都是图像处理中的重要技术&#xff0c;它们的目标是通过分割图像中的不同对象或区域来帮助识别和分析图像&#xff0c;但它们的工作方式和适用场景各有不同。 1. 语义分割&#xff08;Semantic Segme…
阅读更多...
一款基于 Java 的可视化 HTTP API 接口快速开发框架，干掉 CRUD，效率爆炸（带私活源码）

一款基于 Java 的可视化 HTTP API 接口快速开发框架，干掉 CRUD，效率爆炸（带私活源码）

平常我们经常需要编写 API&#xff0c;但其实常常只是一些简单的增删改查&#xff0c;写这些代码非常枯燥无趣。 今天给大家带来的是一款基于 Java 的可视化 HTTP API 接口快速开发框架&#xff0c;通过 UI 界面编写接口&#xff0c;无需定义 Controller、Service、Dao 等 Jav…
阅读更多...
Bolt.new：终极自动化编程工具

Bolt.new：终极自动化编程工具

兄弟们&#xff0c;终极写代码工具来了—— Bolt.new&#xff01;全方位的编程支持&#xff1a; StackBlitz 推出了 Bolt․new&#xff0c;这是一款结合了 AI 与 WebContainers 技术的强大开发平台&#xff0c;允许用户快速搭建并开发各种类型的全栈应用。 它的主要特点是无需…
阅读更多...
内网靶场 | 渗透攻击红队内网域渗透靶场-1（Metasploit）零基础入门到精通，收藏这一篇就够了

内网靶场 | 渗透攻击红队内网域渗透靶场-1（Metasploit）零基础入门到精通，收藏这一篇就够了

“ 和昨天的文章同一套靶场&#xff0c;这次主要使用的是Kali Linux以及Metasploit来打靶场&#xff0c;熟悉一下MSF在内网渗透中的使用&#xff0c;仅供学习参考&#xff0c;大佬勿喷。本期文章靶场来自公众号&#xff1a;渗透攻击红队。” 靶场下载地址&#xff1a;https://…
阅读更多...
展锐平台WIFI国家码信道总结

展锐平台WIFI国家码信道总结

展锐平台WIFI国家码信道总结 1.下载wireless-regdb wireless-regdb是一个开源的工程，编译它会生成regulatory.bin文件，这实际上是一个加密后的数据库，它记录各个国家可用的无线频段。 可从下面的网站上下载最新的regdb库： https://git.kernel.org/pub/scm/linux/kernel…
阅读更多...
【无人水面艇路径跟随控制2】（C++）USV代码阅读： SetOfLos 类的从路径点和里程计信息中计算期望航向

【无人水面艇路径跟随控制2】（C++）USV代码阅读： SetOfLos 类的从路径点和里程计信息中计算期望航向

【无人水面艇路径跟随控制2】&#xff08;C&#xff09;USV代码阅读&#xff1a; SetOfLos 类的从路径点和里程计信息中计算期望航向 写在最前面set_of_los.cpp小结详细解释头文件包含命名空间构造函数和析构函数设置参数函数获取航向函数 &#x1f308;你好呀&#xff01;我是…
阅读更多...
热门：AI变现，看看谁在默默赚大钱？

热门：AI变现，看看谁在默默赚大钱？

在这个愈发依赖AI的时代&#xff0c;找到属于自己的盈利方式愈发重要。 更多实操教程和AI绘画工具,可以扫描下方,免费获取 总的来说&#xff0c;利用AI进行盈利的方式主要有三种&#xff1a;技术型、流量型和内容型。 每种方式都根植于AI的特性&#xff0c;但同时也需要特定…
阅读更多...
最新文章

Copyright @ 2022~2023