代码随想录算法训练营第三十六天 | 188.买卖股票的最佳时机IV 309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费

视频讲的状态 dp[i][0] 是第一次持有之前不操作的状态我都略过这个状态直接从第一次持有的状态开始。因为 dp[i][0] 恒为0。对应地递推公式会有小小改动会下标越界所以加一条判断是否是第一天。func maxProfit(k int, prices []int) int { dp : make([][]int, len(prices)) for i : range dp { dp[i] make([]int, 2*k) } for j : 0; j 2*k; j 2 { dp[0][j] -prices[0] } for i : 1; i len(dp); i { for j : 0; j 2*k; j 2 { //持有 if j 0 { dp[i][j] max(dp[i-1][j], -prices[i]) } else { dp[i][j] max(dp[i-1][j], dp[i-1][j-1]-prices[i]) } //不持有 dp[i][j1] max(dp[i-1][j1], dp[i-1][j]prices[i]) } } return dp[len(dp)-1][2*k-1] }视频讲的dp含义 和 dp含义的顺序 不好理解。我重新定义dp[i][0]持有股票 的最大利润dp[i][1]卖出股票dp[i][2]冷冻期dp[i][3]冷冻期后仍然未持有dp[0][2],dp[0][3]是非法状态初始化只需将第一个状态 dp[1] 带入dp[1][0] max(dp[0][0], dp[0][2]-prices[1], dp[0][3]-prices[1])即可知道dp[0][2],dp[0][3]都应该初始化为0。但做题的时候不用研究这么多ac即可。dp[0][1] 不是非法状态是第一天买入又卖出初始化为0。func maxProfit(prices []int) int { dp : make([][4]int, len(prices)) dp[0][0] -prices[0] dp[0][1] 0 for i : 1; i len(dp); i { dp[i][0] max(dp[i-1][0], dp[i-1][2]-prices[i], dp[i-1][3]-prices[i]) dp[i][1] max(dp[i-1][0] prices[i]) dp[i][2] dp[i-1][1] dp[i][3] max(dp[i-1][2], dp[i-1][3]) } return max(dp[len(dp)-1][1], dp[len(dp)-1][2], dp[len(dp)-1][3]) }不要忘了dp的含义是最大金额所以dp[0][1] 初始化为 0 而不是 -fee-2*fee-3*fee ...func maxProfit(prices []int, fee int) int { dp : make([][2]int, len(prices)) dp[0][0] -prices[0] dp[0][1] 0 for i : 1; i len(dp); 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]-fee) } return dp[len(dp)-1][1] }