動(dòng)態(tài)規(guī)劃
- 思路：
- 假設(shè) dp[i][0] 是第 i 天手上沒有股票時(shí)的最大利潤(rùn)， dp[i][1] 是第 i 天手上有 1 支股票的最大利潤(rùn)；
- dp[i][0] 的遷移狀態(tài)為：
- dp[i - 1][0]，前一天手上已經(jīng)沒有股票，沒有發(fā)生交易；
- dp[i - 1][1] + prices[i]，前一天手上有 1 支股票，第 i 天將其賣掉獲得收益 prices[i]；
- 所以， dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
- 同理?dp[i][1] 的遷移狀態(tài)：
- dp[i - 1][1]，前一天手上有1支股票，第 i 天繼續(xù)持有，不發(fā)生交易；
- dp[i - 1][0] - prices[i]，前一天手上沒有股票，第 i 天買入股票；
- 所以，dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
- 初始狀態(tài)：
- dp[0][0] = 0, dp[0][1] = -prices[0]
- 使用動(dòng)態(tài)規(guī)劃方法將所有可能的值窮舉出來，則最大的收益為 dp[size - 1][0]
class Solution {
public:
int maxProfit(vector<int>& prices) {
int size = prices.size();
int dp[size][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < size; ++i) {
dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[size - 1][0];
}
};文章來源地址http://www.zghlxwxcb.cn/news/detail-777929.html
文章來源：http://www.zghlxwxcb.cn/news/detail-777929.html
到了這里，關(guān)于力扣122. 買賣股票的最佳時(shí)機(jī) II的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[Java·算法·中等] LeetCode122. 買股票的最佳時(shí)機(jī) II 解讀](https://imgs.yssmx.com/Uploads/2024/02/827734-1.jpeg)
