最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

环球今日报丨【算法训练营day49】LeetCode121. 买卖股票的最佳时机 LeetCode122. 买卖股票的最佳时机II

来源：博客园

LeetCode121. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机

独上高楼，望尽天涯路

感觉贪心会更简单，动态规划反而搞复杂了对于这道题。

慕然回首，灯火阑珊处

第一次看题解还是挺难理解的，所以这次写的规范一点。


(资料图)

  1. 确定dp数组及其下标的含义

dp[i][0]表示的是第i天持有股票所得最多现金，通俗一点，就是截止到第i天所能买入股票花费的最少现金。

dp[i][1]表示的是第i天不持有股票所得最多现金，通俗一点，就是截止到第i天卖出股票所赚得的最多现金。

截止是一个关键词，意思是不一定是第i天买入或卖出股票，而是包含第i天及之前所有时间的买入卖出操作。

  1. 确定递推公式

dp[i][0]可以由两个状态推出来，一个是昨天及之前的买入价格更低；另一个是今天的买入价格更低；我们取最好的那个就行。

dp[i][1]也可以由两个状态推出来，一个是昨天及之前已经完成的买入卖出操作赚的更多；另一个是用今天的价格卖出，买入价格用昨天及之前最低的买入价格，赚的更多；我们还是取最好的那个就行。

  1. dp数组如何初始化

dp[0][0]表示第0天最低的买入价格，只能是第0天的买入价格。

dp[0][1]表示第0天卖出所赚得的最多现金，因为第0天不能卖出，所以为0。

  1. 确定遍历顺序

从前向后遍历prices数组即可。

  1. 举例推导dp数组
class Solution {public:    int maxProfit(vector& prices) {        if (prices.size() == 1) return 0;        vector> dp(prices.size(), vector(2));        dp[0][0] = -prices[0];        dp[0][1] = 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], prices[i] + dp[i - 1][0]);        }        return dp[prices.size() - 1][1];    }};

LeetCode122. 买卖股票的最佳时机II

题目链接：122. 买卖股票的最佳时机II

独上高楼，望尽天涯路

没什么思路。

慕然回首，灯火阑珊处

看完题解，猪脑过载，得慢慢消化...

class Solution {public:    int maxProfit(vector& prices) {        vector> dp(prices.size(), vector(2));        dp[0][0] = -prices[0];        dp[0][1] = 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]);        }        return dp[prices.size() - 1][1];    }};

关键词： 望尽天涯路 灯火阑珊处 独上高楼