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

server/2024/10/18 14:17:51/

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

  • 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.ppmy.cn/server/127906.html

相关文章

基于Hive和Hadoop的电商消费分析系统

基于Hive和Hadoop的电商消费分析系统

本项目是一个基于大数据技术的电商消费分析系统&#xff0c;旨在为用户提供全面的电商消费信息和深入的消费行为分析。系统采用 Hadoop 平台进行大规模数据存储和处理&#xff0c;利用 MapReduce 进行数据分析和处理&#xff0c;通过 Sqoop 实现数据的导入导出&#xff0c;以 S…
阅读更多...
使用Node.js的readline模块逐行读取并解析大文件

使用Node.js的readline模块逐行读取并解析大文件

在Node.js环境中处理大文件是一个常见的需求&#xff0c;尤其是在处理日志文件、数据库导出、或任何形式的大规模文本数据时。由于Node.js是基于事件循环和非阻塞I/O的&#xff0c;它非常适合处理这类任务。然而&#xff0c;直接将整个文件内容加载到内存中可能会导致内存溢出&…
阅读更多...
Leetcode—139. 单词拆分【中等】

Leetcode—139. 单词拆分【中等】

2024每日刷题&#xff08;173&#xff09; Leetcode—139. 单词拆分 dp实现代码 class Solution { public:bool wordBreak(string s, vector<string>& wordDict) {int n s.size();unordered_set<string> ust(wordDict.begin(), wordDict.end());vector<b…
阅读更多...
报错Invalid HADOOP_HDFS_HOME

报错Invalid HADOOP_HDFS_HOME

使用env命令查看已有环境变量 果然多了一个变量&#xff0c;因为不需要&#xff0c;所以删除&#xff0c;再次使用env命令查看&#xff0c;无此变量 再输入hadoop,显示正确
阅读更多...
八大排序--01冒泡排序

八大排序--01冒泡排序

假设有一组数据 arr[]{2&#xff0c;0&#xff0c;3&#xff0c;4&#xff0c;5&#xff0c;7} 方法&#xff1a;开辟两个指针&#xff0c;指向如图&#xff0c;前后两两进行比较&#xff0c;大数据向后冒泡传递&#xff0c;小数据换到前面。 一次冒泡后&#xff0c;数组中最大…
阅读更多...
最新BurpSuite2024.9专业中英文开箱即用版下载

最新BurpSuite2024.9专业中英文开箱即用版下载

1、工具介绍 本版本更新介绍 此版本对 Burp Intruder 进行了重大改进&#xff0c;包括自定义 Bambda HTTP 匹配和替换规则以及对扫描 SOAP 端点的支持。我们还进行了其他改进和错误修复。 Burp Intruder 的精简布局我们对 Burp Intruder 进行了重大升级。现在&#xff0c;您可…
阅读更多...
计算机毕业设计Python+Tensorflow股票推荐系统 股票预测系统 股票可视化 股票数据分析 量化交易系统 股票爬虫 股票K线图 大数据毕业设计 AI

计算机毕业设计Python+Tensorflow股票推荐系统 股票预测系统 股票可视化 股票数据分析 量化交易系统 股票爬虫 股票K线图 大数据毕业设计 AI

《PythonTensorflow股票推荐与预测系统》开题报告 一、研究背景与意义 在信息技术高速发展的今天&#xff0c;金融市场日益复杂&#xff0c;投资者面临着越来越多的选择和挑战。股票作为金融市场的重要组成部分&#xff0c;其价格波动受到多种因素的影响&#xff0c;包括宏观…
阅读更多...
WebSocket 2024/9/30

WebSocket 2024/9/30

WebSocket是基于TCP的一种新的网络协议。它实现了浏览器与服务器双工通信——浏览器和服务器只需要完成一次握手&#xff0c;两者之间就可以创建持久性的连接&#xff0c;并进行双向数据传输。 与HTTP协议的区别 实现
阅读更多...
最新文章

Copyright @ 2022~2023