【动态规划】（四）动态规划——打家劫舍与买卖股票

打家劫舍与买卖股票

  • 打家劫舍问题
    • 打家劫舍
    • 打家劫舍II
    • 打家劫舍III
  • 买卖股票问题
    • 买卖股票的最佳时机
    • 买卖股票的最佳时机II
    • 买卖股票的最佳时机III
    • 买卖股票的最佳时机IV
    • 最佳买卖股票时机含冷冻期
    • 买卖股票的最佳时机含手续费
  • 股票问题总结

打家劫舍问题

给定一个数组，相邻的数字不能取，求能取（偷）到的最大数据和。

打家劫舍

力扣链接

示例 1：
输入：[1,2,3,1]
输出：4

示例 2：
输入：[2,7,9,3,1]
输出：12

注意：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

动态规划五部曲

  • dp数组含义： 考虑下标 i（包括i，只考虑，不一定偷）以内的房屋，最多可以偷窃的金额为dp[i]。

  • 确定递推公式：

    • 偷当前前数组，则前一个不能偷：dp[i-2] + nums[i]
    • 不偷当前数据，保持考虑偷前一个的最大值：dp[i-1]
    • 取最大值，所以递推公式为：
      dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

  • 初始化数组：

    dp[0] = 0;
dp[1] = max(nums[0], nums[1]);

  • 确定遍历顺序： 根据递推公式，顺序遍历

  • 举例推导dp数组： 输入[2,7,9,3,1]为例

 
程序实现：

int rob(vector<int>& nums) 
{// dp[i] : 考虑包括下标 i 之前所偷的最大金币 dp[i];//（nums[i]不一定偷，只考虑到）// 结果：dp[nums.size() - 1]// 偷i: dp[i-2] + nums[i]// 不偷i: dp[i-1]// dp[i] = max(dp[i-2] + nums[i], dp[i-1]);//dp[0] = nums[0];//dp[1] = max(nums[0],nums[1]);if(nums.size() == 1)return nums[0];vector<int> dp(nums.size(),0);dp[0] = nums[0];dp[1] = max(nums[0],nums[1]);for(int i = 2; i < nums.size();i++)dp[i] = max(dp[i-2] + nums[i], dp[i-1]);return dp[nums.size() - 1];
}

打家劫舍II

力扣链接

循环数组打家劫舍，即首尾数据算相邻，无法同时偷盗。

示例 ：
输入：nums = [2,3,2]
输出：3
解释：不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

对于一个数组，成环的话主要考虑三种情况：

  • 情况一：考虑不包含首尾元素

 

  • 情况二：考虑包含首元素，不包含尾元素

 

  • 情况三：考虑包含尾元素，不包含首元素

 
情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。

分析到这里，本题其实比较简单了。 剩下的上一题打家劫舍问题完全一样。只需要计算一个区间上的打家窃舍最大值。

程序实现：

class Solution {
public:int rob(vector<int>& nums) {if(nums.size() == 1)return nums[0];// 最后一个数据的下标为 nums.size() - 1int ret1 = robRange(nums, 0, nums.size() - 2);int ret2 = robRange(nums, 1, nums.size() - 1);return max(ret1,ret2);}//计算一个区间上的打家窃舍的最大值int robRange(vector<int>& nums, int start, int end){// dp[i] : 考虑包括下标 i 之前所偷的最大金币 dp[i];//（nums[i]不一定偷，只考虑到）// 结果：dp[end]// 偷i: dp[i-2] + nums[i]// 不偷i: dp[i-1]// dp[i] = max(dp[i-2] + nums[i], dp[i-1]);//dp[start] = nums[start];//dp[start +1 ] = max(nums[start],nums[start+1]);if(start == end)return nums[start];vector<int> dp(nums.size(),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-2] + nums[i], dp[i-1]);return dp[end];}
};

打家劫舍III

力扣原题

二叉树的打家窃舍，相邻节点不能偷。

 
这道题目算是树形dp的入门题目，如果对二叉树遍历不熟悉，就比较有难度。

本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。

与数组的打家窃舍问题一样，关键是要讨论当前节点抢还是不抢

如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（这里说的是“考虑”）

递归三部曲为框架，融合动规五部曲:

  • 1. 确定递归函数的参数和返回值

      这里要求一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组，参数为当前节点，代码如下：

    vector<int> robTree(TreeNode* cur)

    dp数组以及下标含义： 下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

  • 2. 确定终止条件

      在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回，这也相当于dp数组的初始化

    if (cur == NULL) return vector<int>{0, 0}

  • 3. 确定遍历顺序

    使用后序遍历，通过递归函数的返回值来做下一步计算。

    通过递归左节点，得到左节点偷与不偷的金钱。

    通过递归右节点，得到右节点偷与不偷的金钱。

    代码如下：

    // 下标0：不偷，下标1：偷
vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右
// 中

  • 4. 确定单层递归的逻辑

    • 偷当前节点，左右孩子不偷：

      val1 = cur->val + left[0] + right[0];

    • 不偷当前节点，左右孩子各偷一个大的

      val2 = max(leftdp[0],leftdp[1]) + max(rightdp[0], rightdp[1]);

    • 最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

  • 5. 举例推导dp数组

 
最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱

程序实现：

int rob(TreeNode* root) 
{//树形dp引入// dp[2] : 保存当前节点偷与不偷，dp[0] : 不偷当前节点最大金额// 由于递归遍历二叉树，当前层的dp保存当前节点的状态vector<int> ret = robTree(root);return max(ret[0], ret[1]);
}
// 长度为2的数组，0：不偷，1：偷
vector<int> robTree(TreeNode* cur)
{// 后续遍历二叉树if(cur == NULL)return vector<int> {0,0};//向左右遍历vector<int> leftdp  = robTree(cur->left);vector<int> rightdp = robTree(cur->right);// 中间节点偷 左右不偷int value1 = cur->val + leftdp[0] + rightdp[0];// 中间节点不偷 偷左右 int value2 = max(leftdp[0],leftdp[1]) + max(rightdp[0], rightdp[1]);return {value2, value1};
}

买卖股票问题

  • 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格，通过一些列的买卖规则，就散相关所得最多现金。

  • dp[i][j]：表示第 i 天某种状态 j 所得最多现金

  • 例如：

    • dp[i][0] 表示第i天持有股票所得最多现金
    • dp[i][1] 表示第i天不持有股票所得最多现金

  • 注意： 这里是第 i 天持有股票和不持有股票，不代表一定是第 i 天买入，也可以是保持前一天状态。

买卖股票的最佳时机

力扣链接

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

示例 1：
输入：[7,1,5,3,6,4]
输出：5

贪心算法： 因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。

程序实现：

int maxProfit(vector<int>& prices) 
{//[7,1,5,3,6,4]int result = 0;int low = INT_MAX;for(int i = 0; i < prices.size(); i++){low = min(low, prices[i]);				// 获取从左开始的最小值result = max(result, prices[i] - low);	// 获取最大利益}return result;
}

动态规划

动态规划五部曲
1. dp数组含义： dp[i][0] 表示第i天持有股票所得最多现金 ，dp[i][1] 表示第i天不持有股票所得最多现金，注意这里是持有，不是买入。

2. 确定递推公式：

  • 对于当天持有股票有2种情况，当天买入和保持上一天情况

    • 当天买入：dp[i][0] = -prices[i]，只买卖一次，因此一定是第一次买入
    • 保持上一天的情况：dp[i][0] = dp[i-1][0]
    • dp[i][0] = max(dp[i-1][0], -prices[i]);

  • 对于当天不持有股票也有2种情况，当天卖出和保持上一天情况

    • 当天卖出：前一天持有的最大金额 + 卖出获取的金额
      dp[i][1] = dp[i-1][0] + prices[i]
    • 保持：dp[i][1] = dp[i-1][1];
    • dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);

  • 3. 初始化数组： 根据递推公式，需要对dp[0][0]，dp[0][1]初始化

    dp[0][0] = -prices[0];	// 第一天就卖出 手上利润变成-prices[0]元了
dp[0][1] = 0;			// 根据递推公式, dp[0][1] = 0

  • 5. 举例推导dp数组：

 
dp[5][1]即为最终结果：本题中不持有股票状态所得金钱一定比持有股票状态得到的多！

程序实现：

// 动规
int maxProfit(vector<int>& prices) 
{// dp[i][0] 表示第i天持有股票所得最多现金// 第i天买入股票：-prices[i]// 保持不变: dp[i-1][0] // dp[i][1] 表示第i天不持有股票所得最多现金// 第i天卖出股票: dp[i - 1][0] + prices[i] // 保持不变: dp[i-1][1]int len = prices.size();if(len <= 1)return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < len; 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]);}return dp[len-1][1];
}

买卖股票的最佳时机II

  • 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
  • 你可以尽可能地完成更多的交易（多次买卖一支股票）。
  • 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  • 没有交易返回0

示例 1:
输入: [7,1,5,3,6,4]
输出: 7

示例 2:
输入: [1,2,3,4,5]
输出: 4

贪心：本题在贪心章节提及过，一次最大收益的买卖可以分割为每天的收益，因此贪心累加每天的正收益即可。

动规： 该题在买卖股票Ⅰ的题目上进行改进，将只可买卖一次改为可以买卖多次， 因此只需修改持有股票状态下的当天买入股票的表达式：

dp[i][0] = dp[i-1][1] - peices[i]

程序实现：

// 动规
int maxProfit(vector<int>& prices) 
{// dp[i][0] 表示第i天持有股票所得最多现金// 第i天买入股票：dp[i-1][1] - prices[i]  // 保持不变: dp[i-1][0] // dp[i][1] 表示第i天不持有股票所得最多现金// 第i天卖出股票: dp[i - 1][0] + prices[i] // 保持不变: dp[i-1][1]int len = prices.size();if(len <= 1)return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < len; 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]);}return dp[len-1][1];
}

买卖股票的最佳时机III

力扣链接

  • 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

  • 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

  • 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

本题在上述两个题上进行改进，设置买卖次数最多为2次（0-2次均可）

1. 确定dp数组

因为本题可以买卖2次，因此设置5种状态，分别为：

状态表示
0.没有操作dp[i][0]
1.第一次持有股票dp[i][1]
2.第一次不持有股票dp[i][2]
3.第二次持有股票dp[i][3]
4.第二次不持有股票dp[i][4]

2. 确定递推公式

  • 状态0：保持上一天的状态

    dp[i][0] = dp[i-1][0]

  • 状态1：第一次持有股票（当天买入 / 保持上一天已持股）

    • 当天买入：上一天的最大金额 - 当前买股票费用，即 dp[i-1][0] - prices[i]
    • 保持上一天已持股：dp[i-1][1]
    • 所以递推公式为：
      dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])

  • 状态2：第一次不持有股票（当天卖出 / 保持上一天不持股）

    • 当天卖出：上一天持股最大金额 + 当前卖出的收益，即 dp[i-1][1] + prices[i]
    • 保持上一天未持股：dp[i-1][2]
    • 所以递推公式为：
      dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])

  • 状态3：第二次持有股票（当天买入 / 保持上一天已持股）

    • 同理状态1，递推公式为：
      dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3]);

  • 状态4：第二次未持有股票（当天卖出 / 保持上一天未持股）

    • 同理状态2，递推公式为：
      dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4]);

3. 初始化数组：

dp[0][0] = 0;			// 第0天没有操作
dp[0][1] = -prices[0];	// 第0天 第一次买入的操作
dp[0][2] = 0;			// 理解成当天买入 当天卖出
dp[0][3] = -prices[0];	// 当于第0天第一次买入了，第一次卖出了，然后再买入一次,手上没有现金
dp[0][4] = 0;			// 同理dp[0][2]

5. 举例推导dp数组： 以输入[1,2,3,4,5]为例

 
程序实现：

// 动规
int maxProfit(vector<int>& prices) 
{// 一天有五个操作/*dp[i][j]表示第i天状态j后所剩的最大现金0. 没有操作 （其实我们也可以不设置这个状态）dp[i-1][0]1. 第一次持有股票	(1) 第 i 天买入：dp[i-1][0] - prices[i](2）第 i 之前就买入，第 i 天只是保持不动 dp[i-1][1]所以：dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])2. 第一次不持有股票(1) 第 i 天卖出：dp[i-1][1] + prices[i](2) 第 i 天之前卖出，第 i 天只是不变：dp[i-1][2]所以 dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])3. 第二次持有股票同理状态1：dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3])4. 第二次不持有股票同理状态2：dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4])*/int len = prices.size();if(len <= 1)return 0;vector<vector<int>> dp(len, vector<int>(5));dp[0][0] = 0;dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];dp[0][4] = 0;for(int i = 1; i < len; i++){dp[i][0] = dp[i-1][0];dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]);dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2]);dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3]);dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4]);}return max(dp[len-1][2],dp[len-1][4]);
}

买卖股票的最佳时机IV

力扣原题

  • 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
  • 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
  • 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：
输入：k = 2, prices = [2,4,1]
输出：2

示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7

本题是对上题（买卖股票最佳时机III）的更一般化，从最多买卖 k 次延伸到最多买卖 k次，引入k，就是将递归公式一般化

1. dp数组含义：
状态0：不操作
状态1：第一次持有股票    状态2：第一次未持有股票
状态3：第二次持有股票    状态4：第二次未持有股票
.……
状态2 * k - 1：第 k 次持有股票 状态2 * k：第 k 次未持有股票

2. 确定递推公式：
将上一题的递推公式一般化，通过找规律，上一题递推公式如下：

k = 2
保持状态
dp[i][0] = dp[i-1][0];
第一次 买卖
dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]);
dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2]);
第二次买卖
dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3]);
dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4]);

引入k，将公式推广一般化：

for(int i = 1; i < len; i++)
{dp[i][0] = dp[i-1][0];// 1 3 5for(int j = 1; j < 2 * k; j += 2){dp[i][j] = max(dp[i-1][j-1] - prices[i], dp[i-1][j]);		// 买入dp[i][j+1] = max(dp[i-1][j] + prices[i], dp[i-1][j+1]);		// 卖出}
}

3. 初始化数组：

第0天买入后所剩余的现金均为 -prices[0]，卖出后的现金剩余均为0

vector<vector<int>> dp(len, vector<int>(2 * k + 1, 0));
//初始化
for(int i = 1; i < 2 * k; i += 2)dp[0][i] = -prices[0];

5. 举例推导dp数组： 以输入[1,2,3,4,5]，k=2为例

 
程序实现：

// 动规
int maxProfit(int k, vector<int>& prices) 
{// 由于最多 k 次，一天相当于有 2 * k + 1 个操作/*dp[i][j]表示第i天状态j后所剩的最大现金0. 没有操作 （其实我们也可以不设置这个状态）dp[i-1][0]1. 第一次持有股票	(1) 第 i 天买入：dp[i-1][0] - prices[i](2）第 i 之前就买入，第 i 天只是保持不动 dp[i-1][1]所以：dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])2. 第一次不持有股票(1) 第 i 天卖出：dp[i-1][1] + prices[i](2) 第 i 天之前卖出，第 i 天只是不变：dp[i-1][2]所以 dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])3. 第二次持有股票同理状态1：dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3])4. 第二次不持有股票同理状态2：dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4])......// j = 1 3 5第 k 次持有股票：  dp[i][j] = max(dp[i-1][j-1] - prices[i], dp[i-1][j]);第 k 次不持有股票: dp[i][j] = max(dp[i-1][j-1] + prices[i], dp[i-1][j]);*/int len = prices.size();if(len <= 1)return 0;vector<vector<int>> dp(len, vector<int>(2 * k + 1, 0));//初始化for(int i = 1; i < 2 * k; i += 2)dp[0][i] = -prices[0];//递推公式 k = 2for(int i = 1; i < len; i++){dp[i][0] = dp[i-1][0];// 1 3 5for(int j = 1; j < 2 * k; j += 2){dp[i][j] = max(dp[i-1][j-1] - prices[i], dp[i-1][j]);		// 买入dp[i][j+1] = max(dp[i-1][j] + prices[i], dp[i-1][j+1]);		// 卖出}}return dp[len-1][2 * k];
}

最佳买卖股票时机含冷冻期

力扣链接

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

分析

  • 本题相对于 买卖股票的最佳时机II 多出了一个冷冻期，
  • 因此需要对之前未持有股票的状态进行分解为2个状态：保持股票卖出状态和当日卖出股票的状态
  • 同时还需一个冷冻期的状态

1. dp数组含义：

状态表示含义
状态0dp[i][0]表示第 i 天 持有股票的最多现金
状态1dp[i][1]表示第 i 天 保持股票卖出的最多现金
状态2dp[i][2]表示第 i 天 股票卖出后最多现金
状态3dp[i][3]表示第 i 天为 冷冻期时的最多现金

2. 确定递推公式：

  • 状态0：持有股票（当天买入 / 保持上一天已经持有）

    • 保持上一天已持有：dp[i-1][0]

    • 第 i 天买入股票，也有两种情况

      • 前一天是冷冻期： dp[i-1][3] - prices[i]
      • 前一天是保持股票卖出状态：dp[i-1][1] - prices[i]

    • 所以

      dp[0][i] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);

  • 状态1： 保持股票卖出的状态

    • 保持前一天的卖出状态：dp[i-1][1]
    • 冷冻期后一天：dp[i-1][3]
    • 所以，递推公式为：
      dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

  • 状态2：表示第 i 天卖出股票的状态

    • 前一天肯定持股，所以递推公式为：
      dp[i][2] = dp[i - 1][0] + prices[i];

  • 状态3：冷冻期状态

    • 昨天卖股票，所以递推公式为：
      p[i][3] = dp[i-1][2]

3. dp数组如何初始化

dp[0][0] = -prices[0];	// 当天买入股票。
dp[0][1] = 0;
dp[0][2] = 0;
dp[0][3] = 0;

5. 举例推导dp数组： 以 [1,2,3,0,2] 为例，dp数组如下：

 

程序实现：

// 动规
int maxProfit(vector<int>& prices) 
{// 状态0：// dp[i][0] 表示第i天持有股票所得最多现金// 保持不变: dp[i-1][0] // 第i天买入股票：// 冷冻期后一天买入：dp[i-1][3] - prices[i]// 保持买入股票状态：dp[i-1][1] - prices[i]// 状态1：// dp[i][1] 保持股票卖出的状态// 保持不变：dp[i-1][1]// 冷冻期后一天也是保持卖出的状态，前一天是冷冻期，dp[i-1][3]// 状态2：// dp[i][2] 表示第i天卖出股票的状态,前一天肯定持股// 第i天卖出股票: dp[i][2] = dp[i-1][0] + prices[i] // 状态3：// dp[i][3]: 冷冻期//冷冻期前一天肯定是卖出股票 dp[i][3] = dp[i-1][2]int len = prices.size();if(len <= 1)return 0;vector<vector<int>> dp(len, vector<int>(4));dp[0][0] = -prices[0];dp[0][1] = 0;dp[0][2] = 0;dp[0][3] = 0;for(int i = 1; i < len; i++){dp[i][0] = max(dp[i-1][0], max(dp[i-1][1] - prices[i], dp[i-1][3] - prices[i]));dp[i][1] = max(dp[i-1][3], dp[i-1][1]);dp[i][2] = dp[i-1][0] + prices[i];dp[i][3] = dp[i-1][2];			}return max(dp[len-1][1], max(dp[len-1][2], dp[len-1][3]));
}

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

力扣链接

  • 给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

  • 可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

  • 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8

本题在 买卖股票的最佳时机II 的题目上进行更改，只需将每次在第i天不持有股票所得最多现金状态下，每次卖出股票时候扣除手续费即可，表示结束一轮交易。

dp[i][1] = dp[i-1][0] + prices[i] - fee

确定dp数组含义

状态0：

  • dp[i][0] 表示第 i 天持有股票所得最多现金
  • 保持不变: dp[i-1][0]
  • 第i天买入股票：dp[i-1][1] - prices[i]

状态1：

  • dp[i][1] 表示第i天不持有股票所得最多现金
  • 保持不变：dp[i-1][1]
  • 卖出：dp[i][1] = dp[i-1][0] + prices[i] - fee

程序实现：

// 动规
int maxProfit(vector<int>& prices, int fee) 
{// 状态0：// dp[i][0] 表示第i天持有股票所得最多现金// 保持不变: dp[i-1][0] // 第i天买入股票：dp[i-1][1] - prices[i]// 状态1：// dp[i][1] 表示第i天不持有股票所得最多现金// 保持不变：dp[i-1][1]// 卖出：dp[i][1] = dp[i-1][0] + prices[i] - feeint len = prices.size();if(len <= 1)return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < len; 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 max(dp[len-1][0], dp[len-1][1]);
}

股票问题总结

股票问题总结

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

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

相关文章

day-59 两两交换链表中的节点

day-59 两两交换链表中的节点

思路 只需将链表两两交换节点即可&#xff0c;如果是奇数个节点&#xff0c;最后一个节点则不用交换 解题过程 可以先自定义一个头结点thead&#xff0c;这样更便于思考交换&#xff0c;最后返回thead.next即可 Code /*** Definition for singly-linked list.* public class…
阅读更多...
SAM+无监督学习！能发顶会的高端局组合！idea效果绝佳

SAM+无监督学习！能发顶会的高端局组合！idea效果绝佳

学过SAM的朋友都知道&#xff0c;SAM需要对训练数据进行全面的手动标记&#xff0c;每张图像都要超过20分钟...效率有待提升。那么如何解决这个短板&#xff1f;我们考虑SAM无监督学习。 这是因为无监督学习具有无需人工标注数据的特点&#xff0c;通过将两者结合&#xff0c;…
阅读更多...
【LeetCode】动态规划—删除并获得点数（附完整Python/C++代码）

【LeetCode】动态规划—删除并获得点数（附完整Python/C++代码）

动态规划—#740. 删除并获得点数 前言题目描述基本思路1. 问题定义:2. 理解问题和递推关系:3. 解决方法:4. 进一步优化:5. 小总结: 代码实现Python3代码实现Python 代码解释C代码实现C 代码解释 总结: 前言 给你一个整数数组 n u m s nums nums &#xff0c;你可以对它进行一…
阅读更多...
DownShift: Tuning Shift Reduction With Reliability for Racetrack Memories

DownShift: Tuning Shift Reduction With Reliability for Racetrack Memories

目录 DownShift: Tuning Shift Reduction With Reliability for Racetrack Memories文章摘要&#xff1a;文章的主要贡献包括&#xff1a;文章的结构如下&#xff1a;DownShiftDownShift通过以下方式改进了现有的数据放置策略&#xff1a; GROGU&#xff08;Generating Reliabi…
阅读更多...
2024最受欢迎的3款｜数据库管理和开发｜工具

2024最受欢迎的3款｜数据库管理和开发｜工具

1.SQLynx&#xff08;原SQL Studio&#xff09; 概述&#xff1a; SQLynx是一个原生基于Web的SQL编辑器&#xff0c;由北京麦聪软件有限公司开发。它最初被称为SQL Studio&#xff0c;后改名为SQLynx&#xff0c;支持企业的桌面和Web数据库管理。SQLynx支持所有流行的数据库&a…
阅读更多...
工业一体机实现接口与模块选配

工业一体机实现接口与模块选配

在现代工业自动化和智能制造的浪潮中&#xff0c;工业一体机因其集成化、稳定性高和适应性强的特性而逐渐成为企业生产过程中不可或缺的设备。为了满足不同客户的需求&#xff0c;工业一体机的接口与模块选配功能显得尤为重要。 一、工业一体机的基本概念 工业一体机是将计算、…
阅读更多...
跟着B战学习JAVA面试八股文

跟着B战学习JAVA面试八股文

学习链接&#xff1a;https://www.bilibili.com/video/BV1gm411S7EX/?spm_id_from333.337.search-card.all.click&vd_sourceefbaa07876b231ae3225ba8999116807 创建线程的几种方式&#xff1f; 继承Thread类实现Runnable接口实现Callable接口通过线程池来创建线程 为什么…
阅读更多...
【官方Mamba库】原理简述和代码解析

【官方Mamba库】原理简述和代码解析

目录 1 代码原理简述1.1 原始结构——SSM1.2 结构改进——S4&#xff08;Structured State Space for Sequences&#xff09;1.2.1 离散化1.2.2HiPPO 1.3 最终版本——Mamba&#xff08;又称S6或selective SSMs&#xff09; 2 代码库目录结构2.1 mamba_simple.py主体结构2.1.1 …
阅读更多...
OLED（2）驱动篇

OLED（2）驱动篇

文章目录 1 概述2 代码简述2.1 OLED 对象2.2 OLEDProtocol 对象2.3 OLEDFont 对象 3 成果展示 1 概述 1&#xff09;代码仓库&#xff1a;这里尝试了两种面向对象的方式&#xff0c;不足之处敬请指正。 OOP 方式&#xff1a;https://gitee.com/luyaocf/demo-jlc_stm32f407_oop.…
阅读更多...
Unity 设计模式 之 行为型模式-【命令模式】【责任链模式】

Unity 设计模式 之 行为型模式-【命令模式】【责任链模式】

Unity 设计模式 之 行为型模式-【命令模式】【责任链模式】 目录 Unity 设计模式 之 行为型模式-【命令模式】【责任链模式】 一、简单介绍 二、命令模式&#xff08;Command Pattern&#xff09; 1、什么时候使用命令模式 2、使用命令模式的好处 3、使用时的注意事项 三…
阅读更多...
FME学习笔记

FME学习笔记

读取数据 方法一&#xff1a;add reader 通过读模块来进行数据的读取 方法二&#xff1a;FeatureReader Parameters 通过转换器来进行数据的读取 可以通过空间范围进行筛选 在FME中&#xff0c;所有数据处理都要用到的&#xff0c;绝对的重点&#xff1a;转换器&#xff…
阅读更多...
【Python】PyCharm: 强大的 Python 开发环境

【Python】PyCharm: 强大的 Python 开发环境

⭕️宇宙起点 &#x1f4e2; 引言&#x1f3ac; 什么是 PyCharm&#xff1f;&#x1f528; PyCharm 的核心特性1. 智能代码编辑2. 调试和测试3. 项目和代码结构导航4. 集成 AI 助手5. 远程开发6. 集成数据库7. 科学工具8. 版本控制集成9. Web 开发 &#x1f4e6; 安装 PyCharm&…
阅读更多...
黑马智数Day4-1

黑马智数Day4-1

新增月卡 配置路由完成跳转 {path: /cardAdd,component: () > import(/views/car/car-card/add-card) }<el-button type"primary" click"$router.push(/cardAdd)">添加月卡</el-button> 车辆信息表单验证 <el-form :model"carInf…
阅读更多...
Bug：ThreadPoolTaskScheduler搭配CronTask完成定时任务，关闭scheduler后CronTask任务仍然执行？

Bug：ThreadPoolTaskScheduler搭配CronTask完成定时任务，关闭scheduler后CronTask任务仍然执行？

【问题】执行下面代码后&#xff0c;关闭ThreadPoolTaskScheduler&#xff0c;CronTask仍然继续执行。 Configuration public class config {Beanpublic String getString() throws InterruptedException {Runnable runnable () -> {try {System.out.println("hello r…
阅读更多...
《程序猿之设计模式实战 · 适配器模式》

《程序猿之设计模式实战 · 适配器模式》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; CSDN入驻不久&#xff0c;希望大家多多支持&#xff0c;后续会继续提升文章质量&#xff0c;绝不滥竽充数…
阅读更多...
【后端开发】JavaEE初阶—线程安全问题与加锁原理（超详解）

【后端开发】JavaEE初阶—线程安全问题与加锁原理（超详解）

前言&#xff1a; &#x1f308;上期博客&#xff1a;【后端开发】JavaEE初阶—Theard类及常见方法—线程的操作&#xff08;超详解&#xff09;-CSDN博客 &#x1f308;感兴趣的小伙伴看一看小编主页&#xff1a;GGBondlctrl-CSDN博客 &#x1f308;小编会在后端开发的学习中不…
阅读更多...
关于javascript中防抖和节流的使用详解

关于javascript中防抖和节流的使用详解

防抖&#xff08;Debounce&#xff09;和节流&#xff08;Throttle&#xff09;是两种常见的优化技巧&#xff0c;通常用于控制函数在短时间内频繁触发的场景&#xff0c;尤其是在处理用户输入、滚动、窗口大小调整等事件时。它们的主要目的是减少不必要的函数调用&#xff0c;…
阅读更多...
超详细超实用！！！AI编程之cursor编写设计模式开闭原则实例（四）

超详细超实用！！！AI编程之cursor编写设计模式开闭原则实例（四）

云风网 云风笔记 云风知识库 一、设计模式开闭原则定义 当应用的需求改变时&#xff0c;在不修改软件实体&#xff08;项目模块、类、接口方法&#xff09;的源代码或者二进制代码的前提下&#xff0c;可以扩展模块的功能&#xff0c;使其满足新的需求。即软件实体应当对扩展开…
阅读更多...
【Linux】nginx连接前端项目

【Linux】nginx连接前端项目

文章目录 一、项目编译1.编译文件2.dist文件 二、Linux nginx配置三、启动nginx 一、项目编译 1.编译文件 2.dist文件 二、Linux nginx配置 在Xshell软件中&#xff0c;点击CtrlAltF进入文件传输找到地址&#xff1a;/usr/local/nginx/html将dist文件传入 找到nginx.conf&…
阅读更多...
git add成功后忘记commit的文件丢了？

git add成功后忘记commit的文件丢了？

本文目标&#xff1a;开发人员&#xff0c;在了解git fsck命令用法的条件下&#xff0c;进行git add成功但由于误操作导致丢失的文件找回&#xff0c;达到找回丢失文件的程度。 文章目录 1 痛点2 解决方案3 总结/练习 1 痛点 开发过程中&#xff0c;分支太多&#xff08;基线分…
阅读更多...
最新文章

Copyright @ 2022~2023