代码随想录算法训练营19期第50天

 123.买卖股票的最佳时机III  

视频讲解：动态规划，股票至多买卖两次，怎么求？ | LeetCode：123.买卖股票最佳时机III_哔哩哔哩_bilibili

代码随想录  

初步思路：买卖股票的最佳时机I。

总结：

关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖.

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金.

五个状态:

0: 没有操作; 1:第一次持有股票; 2:第一次不持有股票; 3:第二次持有股票; 4:第二次不持有股票

五个递推公式:

            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])

用时：60分钟

 188.买卖股票的最佳时机IV  

视频讲解：动态规划来决定最佳时机，至多可以买卖K次！| LeetCode：188.买卖股票最佳时机4_哔哩哔哩_bilibili

代码随想录

初步思路：买卖股票的最佳时机III。

dp[i][j]中 i表示第i天，j为 [0 – 2k] 个状态，dp[i][j]表示第i天状态j所剩最大现金.

2k个状态:

0: 没有操作; 1:第一次持有股票; 2:第一次不持有股票; 3:第二次持有股票; 4:第二次不持有股票; ….

2k-1:第k次持有股票; 2k:第k次不持有股票;

2k个递推公式:

            j is odd                   ->           dp[i][j] = max(dp[i - 1][j], dp[i - 1][j-1] - prices[i])

            j is even                  ->           dp[i][j] = max(dp[i - 1][j], dp[i - 1][j-1] + prices[i])

用时：45分钟