关于动态规划【力扣123.买卖股票的最佳时机III的思考】

关于动态规划【力扣123.买卖股票的最佳时机III的思考】

1、与前两题的区别

【力扣121.买卖股票的最佳时机I】只能买卖1次

【力扣122.买卖股票的最佳时机II】可以买卖多次

【力扣123.买卖股票的最佳时机III】只能买卖2次

2、关键区别

dp数组的状态表示变多了,有四种。

(但是dp数组本身的含义递推关系都和前两题差不多)

3、注意点

【最后返回的数值问题】

因为不持有的最大利润一定比持有的最大利润多,所以在dp[i][2]和dp[i][4]之间返回就行。

又因为第二次不持有的最大利润在计算的时候已经包含了第一次不持有的最大利润,所以第二次不持有的最大利润一定比第一次不持有的最大利润多,所以返回dp[i][4]就行。