121. 买卖股票的最佳时机
五部曲:
dp数组下标及含义:dp[i][0] 表示第i天持有股票所得最多现金 ;dp[i][1] 表示第i天不持有股票所得最多现金
dp数组初始化:dp[0][0] -= prices[0];dp[0][1] = 0;
递推公式: dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
遍历方向:从前到后遍历
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if (len == 0)
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], prices[i] + dp[i - 1][0]);
}
return dp[len - 1][1];
}
};
122.买卖股票的最佳时机II
五部曲:
dp数组下标及含义:dp[i][0] 表示第i天持有股票所得最多现金 ;dp[i][1] 表示第i天不持有股票所得最多现金
dp数组初始化:dp[0][0] -= prices[0];dp[0][1] = 0;
递推公式: dp[i][0] = max(dp[i - 1][0], dp[i-1][1]-prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
遍历方向:从前到后遍历
本题和上一题不同之处在于股票可以多次买卖,因此,在第i天买入股票的情况会出现当天卖出再买入。所以dp[i][0]的递推公式要有所变化。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(len, vector<int>(2, 0));
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];
}
};