123. 买卖股票的最佳时机 III - 力扣（Leetcode）
思路:
-
使用动态规划
-
-
确定dp数组以及下标的含义
dp[i][j]的定义为：dp[i][0]没有意义，仅用于占位，dp[i][1]代表第一次持有股票的现金最大值，dp[i][2]代表第一次不持有股票的现金最大值，dp[i][3]代表第二次持有股票的现金最大值，dp[i][4]代表第二次不持有股票的现金最大值
-
确定递推公式
// 状态转移方程 // dp[i][1]有两种状态，一种是本身就持有，那么值从dp[i - 1][1]演变而来 // 另一种是本身不持有，要购买一支股票，那么值就是-prices[i]，取两者最大值 dp[i % 2][1] = max(dp[(i - 1) % 2][1], -prices[i]); // dp[i][2]有两种状态，一种是本身就不持有，那么值从dp[i - 1][2]演变而来 // 另一种是今天卖了手上的股票，那么值就是dp[i - 1][1] + prices[i]，取两者最大值 dp[i % 2][2] = max(dp[(i - 1) % 2][2], dp[(i - 1) % 2][1] + prices[i]); // dp[i][3]有两种状态，一种是本身就持有，那么值从dp[i - 1][3]演变而来 // 另一种是本身不持有，要购买一支股票，但是此时的值要继承第一次不持有股票的值 // 所以此时的值就是dp[i - 1][2] - prices[i] dp[i % 2][3] = max(dp[(i - 1) % 2][3], dp[(i - 1) % 2][2] - prices[i]); // dp[i][4]有两种状态，一种是本身就不持有，那么值从dp[i - 1][4]演变而来 // 另一种是今天卖了手上的股票，那么值就是dp[i - 1][3] + prices[i]，取两者最大值 dp[i % 2][4] = max(dp[(i - 1) % 2][4], dp[(i - 1) % 2][3] + prices[i]); -
dp数组如何初始化
vector< vector<int> > dp(2, vector<int>(5, 0)); dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; -
确定遍历顺序
因为i = 0已经初始化，所以从i = 1开始从前往后遍历
-
我的AC代码
// 时间复杂度O(n),空间复杂度O(1) class Solution { public: int maxProfit(vector<int>& prices) { vector< vector<int> > dp(2, vector<int>(5, 0)); int len = prices.size(); dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for(int i = 1; i < len; ++i) { dp[i % 2][1] = max(dp[(i - 1) % 2][1], -prices[i]); dp[i % 2][2] = max(dp[(i - 1) % 2][2], dp[(i - 1) % 2][1] + prices[i]); dp[i % 2][3] = max(dp[(i - 1) % 2][3], dp[(i - 1) % 2][2] - prices[i]); dp[i % 2][4] = max(dp[(i - 1) % 2][4], dp[(i - 1) % 2][3] + prices[i]); } return dp[(len - 1) % 2][4]; } };
标准答案
空间复杂度高但便于理解
// 时间复杂度O(n),空间复杂度O(n) // 这个版本空间复杂度高，但是便于理解 class Solution { public: int maxProfit(vector<int>& prices) { if (prices.size() == 0) return 0; vector<vector<int>> dp(prices.size(), vector<int>(5, 0)); dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for (int i = 1; i < prices.size(); i++) { dp[i][0] = dp[i - 1][0]; 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]); dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]); } return dp[prices.size() - 1][4]; } };
空间复杂度低但不易于理解
// 时间复杂度O(n),空间复杂度O(1) // 空间复杂度低但不易于理解 class Solution { public: int maxProfit(vector<int>& prices) { if (prices.size() == 0) return 0; vector<int> dp(5, 0); dp[1] = -prices[0]; dp[3] = -prices[0]; for (int i = 1; i < prices.size(); i++) { dp[1] = max(dp[1], dp[0] - prices[i]); dp[2] = max(dp[2], dp[1] + prices[i]); dp[3] = max(dp[3], dp[2] - prices[i]); dp[4] = max(dp[4], dp[3] + prices[i]); } return dp[4]; } };
188. 买卖股票的最佳时机 IV - 力扣（Leetcode）
思路:
-
使用动态规划，这道题和123. 买卖股票的最佳时机 III - 力扣（Leetcode）的最大区别就是最大交易次数不同，本题最大交易次数是k次，而123. 买卖股票的最佳时机 III - 力扣（Leetcode）最大交易次数是固定的2次，写上一题的时候我就在想有没有可能会出一道题让交易次数可变，没想到还真有，理清逻辑，掌握交易背后的本质是写出这道题的关键
-
我们用时间复杂度较高但较好理解的解法来做解析
-
-
确定dp数组以及下标的含义
dp[i][j]的定义为：dp[i][0]没有意义，仅用于占位，dp[i][k * 2 + 1]代表第k + 1次持有股票的现金最大值，dp[i][k * 2 + 2]代表第k + 1次不持有股票的现金最大值
-
确定递推公式
// 状态转移方程 for(int j = 1; j <= k * 2; ++j) { // dp[i][j](j为单数)有两种状态，一种是本身就持有，那么值从dp[i - 1][j]演变而来 // 另一种是本身不持有，要购买一支股票，其值要从上一次卖出股票那里继承 // 如果是第一次买股票就是从dp[i][0]那里继承 // 那么值就是dp[i - 1][j - 1] - prices[i]，取两者最大值 if(j % 2 == 1) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]); } // dp[i][j](j为双数)有两种状态，一种是本身就不持有，那么值从dp[i - 1][j]演变而来 // 另一种是卖了手上的股票，其值要从上一次持有股票那里继承 // 那么值就是dp[i - 1][j - 1] + prices[i]，取两者最大值 else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]); } } -
dp数组如何初始化
vector< vector<int> > dp(prices.size(), vector<int>(k * 2 + 1, 0)); for(int i = 1; i <= k * 2; ++i) { if(i % 2 == 1) { dp[0][i] = -prices[0]; } } -
确定遍历顺序
因为i = 0已经初始化，所以从i = 1开始从前往后遍历
-
我的AC代码
空间复杂度高
// 时间复杂度O(n * k),空间复杂度O(n * k) class Solution { public: int maxProfit(int k, vector<int>& prices) { vector< vector<int> > dp(prices.size(), vector<int>(k * 2 + 1, 0)); for(int i = 1; i <= k * 2; ++i) { if(i % 2 == 1) { dp[0][i] = -prices[0]; } } for(int i = 1; i < prices.size(); ++i) { for(int j = 1; j <= k * 2; ++j) { if(j % 2 == 1) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]); } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]); } } } return dp[prices.size() - 1][k * 2]; } };
优化空间复杂度
// 时间复杂度O(n * k),空间复杂度O(k) class Solution { public: int maxProfit(int k, vector<int>& prices) { vector<int> dp(k * 2 + 1, 0); for(int i = 1; i <= k * 2; ++i) { if(i % 2 == 1) { dp[i] = -prices[0]; } } for(int i = 1; i < prices.size(); ++i) { for(int j = 1; j <= k * 2; ++j) { if(j % 2 == 1) { dp[j] = max(dp[j], dp[j - 1] - prices[i]); } else { dp[j] = max(dp[j], dp[j - 1] + prices[i]); } } } return dp[k * 2]; } };
标准答案
// 时间复杂度O(n * k),空间复杂度O(n * k) class Solution { public: int maxProfit(int k, vector<int>& prices) { if (prices.size() == 0) return 0; vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0)); for (int j = 1; j < 2 * k; j += 2) { dp[0][j] = -prices[0]; } for (int i = 1;i < prices.size(); i++) { for (int j = 0; j < 2 * k - 1; j += 2) { dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]); dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); } } return dp[prices.size() - 1][2 * k]; } };
Comments NOTHING