188. 买卖股票的最佳时机 IV(困难)
class Solution {public int maxProfit(int k, int[] prices) {int dp[][] = new int[k][2];for(int i=0;i<k;i++){dp[i][0] = -prices[0];dp[i][1] = 0;}for(int i=1;i<prices.length;i++){int sell = 0;for(int j=0;j<k;j++){dp[j][0] = Math.max(dp[j][0],sell-prices[i]);dp[j][1] = Math.max(dp[j][1],prices[i]+dp[j][0]);sell = dp[j][1];}}return dp[k-1][1];}
}
309. 最佳买卖股票时机含冷冻期（中等）
思路：思考每一个 dp 节点可能的情况，然后寻找产生这些情况的各种可能，利用这些可能推递推公式。
class Solution {public int maxProfit(int[] prices) {int n = prices.length;int dp[][] = new int[n][3];dp[0][0] = -prices[0];for(int i=1;i<n;i++){dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);dp[i][1] = dp[i-1][0]+prices[i];dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]);}return Math.max(dp[n-1][1],dp[n-1][2]);}
}
714. 买卖股票的最佳时机含手续费(中等)
思路：两种可能，持有股票/不持有股票
持有股票：可能是昨天就持有，也可能昨天卖掉之后今天又买
不持有股票：可能是昨天就不持有或者昨天持有今天刚卖掉
class Solution {public int maxProfit(int[] prices, int fee) {int n = prices.length;int dp[][] = new int[n][2];dp[0][0] = -prices[0];for(int i=1;i<n;i++){dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);}return dp[n-1][1];}
}
股票问题总结
6 道题，分了两大类，一种是无限次买，另一种限制购买次数。
对于无限制买情况，确定好每次购买的状态，推导状态产生的原因，取最大值。
对于限制购买次数的情况，分梯队计算，梯队每加一层，都会在前一个梯队的最大值基础上，再加上这次的利润。
