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

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];}
};