1、基础问题
只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
class Solution { public int maxProfit(int[] prices) { int n = prices.length; int pre = prices[0]; //记录可买入的最小值 int ans = Integer.MIN_VALUE; //记录当下得到的最大收益 for(int i = 0; i < n; i++){ ans = Math.max(ans, prices[i] - pre); pre = Math.min(pre, prices[i]); } return ans; } }2、冷冻期
在满足以下约束条件——卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)，你可以尽可能地完成更多的交易（多次买卖一支股票）。
在这个问题中，需要考虑两个问题：
1、卖出后的第二天是不能操作的，在这里初始化数组时可以类比打家劫舍问题的初始化；
2、可以多次买入卖出，那么第i天可能是买入/卖出状态，所以需要增加一维来记录每天可能发生的情况。
如果第i+2天是卖出状态（不持有股票）， 那么可能发生的情况是：
- 第i+1天也不持有且没有买入操作；
- 第i天持有且卖出。
如果第i+2天是买入状态（持有股票），那么可能发生的情况是：
- 第i+1天已经持有且没有卖出操作；
- 第i天是未持有但是进行了买入操作。
class Solution { public int maxProfit(int[] prices) { int n = prices.length; // 含冷冻期：类比打家劫舍 //两列，分别代表pre和ans int[][] dp = new int[n + 2][2]; dp[1][1] = Integer.MIN_VALUE; for(int i = 0; i < n; i++){ // dp[t][0]：第t天结束，不持有股票的最大利润 dp[i + 2][0] = Math.max(dp[i + 1][0], dp[i + 1][1] + prices[i]); // dp[t][1]：第t天结束，持有股票的最大利润 dp[i + 2][1] = Math.max(dp[i + 1][1], dp[i][0] - prices[i]); } return dp[n + 1][0]; } }3、手续费
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
迭代思路与上一个问题大致相同，区别在于没有冷冻期，所以第i+1天的收益只与第i天有关；
手续费在每次交易中只扣除一次，可以固定在卖出时扣除，便于理解。
class Solution { public int maxProfit(int[] prices, int fee) { int n = prices.length; // x:没有冷冻期 // y:0——第i天不持有股票；1——第i天持有股票 int[][] dp = new int[n + 1][2]; dp[0][1] = Integer.MIN_VALUE / 2; for(int i = 0; i < n; i++){ // 如果第i+1天为不持有股票状态，那么第i天如果也不持有，二者收益相同；如果持有，那么就可以卖出获得收益，同时要付出一定的手续费。 dp[i + 1][0] = Math.max(dp[i][0], dp[i][1] + prices[i] - fee); // 如果第i+1天为持有股票状态，那么第i天如果也持有，二者收益相同；如果不持有，那么就可以买入。 dp[i + 1][1] = Math.max(dp[i][0] - prices[i], dp[i][1]); } return dp[n][0]; } }4、设定交易上限
设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。也就是说，你最多可以买k次，卖k次。
简单理解就是多了一个维度的限制——交易次数
（如果从三维角度不好理解，可以先参考空间优化的方案，直观理解一下对交易次数的约束）
我认为这里理解的难点在于初始化的部分：
- y的大小：交易次数
j的取值范围是0,1,2,...,k，一共k+1种次数状态，数组第二维必须开到k+1才能容纳全部次数，为了不越界，数组长度开到k+2； - 初始化为Integer.MIN_VALUE / 2的部分：标记所有状态初始为「不可达非法状态」——在第 0 天（无任何操作），不存在任何买卖行为，不管是持有股票、还是完成任意笔交易，都无法实现，全部置极小值。
- 初始化为0的部分：
f[0][j][0] = 0——还没处理任何一天（i=0），视作已经完成 j 笔交易、且手上无股票，利润为 0
class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; int[][][] f = new int[n + 1][k + 2][2]; // x:第i天；y:第j次；z:第i天卖出状态——0，买入——1 // 初始化为最小值 for(int[][] s : f){ for(int [] row : s){ Arrays.fill(row, Integer.MIN_VALUE / 2); } } for(int j = 1; j <= k + 1; j++){ f[0][j][0] = 0; } for(int i = 0; i < n; i++){ for(int j = 1; j <= k + 1; j++){ f[i + 1][j][0] = Math.max(f[i][j][0], f[i][j][1] + prices[i]); f[i + 1][j][1] = Math.max(f[i][j - 1][0] - prices[i], f[i][j][1]); } } return f[n][k + 1][0]; } }空间优化
相当于把每天的收益变化存储优化到一维，每次迭代后直接在原位置进行修改：
如果在迭代过程中发生了买入操作，就说明前一天的交易次数是j-1；如果没有操作或者卖出都不会修改交易次数（相当于由买入这个动作触发交易次数的变化）。
初始化：
- 初始化为Integer.MIN_VALUE / 2的部分：所有
dp[j][1]（持有股票状态），k>=1的初始时刻不可能持有股票，持股状态标记为不可达（极小值）。 - 初始化为0的部分：k为偏移设计，实际计算到k=1，所以k=0标记为不可达。
class Solution { public int maxProfit(int k, int[] prices) { // 空间优化 int n = prices.length; int[][] f = new int[k + 2][2]; for(int j = 1; j < k + 2; j++){ f[j][1] = Integer.MIN_VALUE / 2; } f[0][0] = Integer.MIN_VALUE / 2; for(int x : prices){ for(int j = k + 1; j > 0; j--){ f[j][0] = Math.max(f[j][0], f[j][1] + x); f[j][1] = Math.max(f[j - 1][0] - x, f[j][1]); } } return f[k + 1][0]; } }变形：刚好k次完成
在迭代结束后判断f[k+1][0]是否为极小，如果是，说明小于k次就完成了交易，不满足题意。
//必须恰好k笔，取f[k+1][0]，若还是极小说明凑不齐k笔，返回0 int res = f[k + 1][0]; return res < 0 ? 0 : res;变形：至少k次完成
1、根据prices数组判断：是否可以至少完成k次交易？至多可以完成几次交易maxT？
2、后续基于maxT算收益；
3、遍历[k, maxT]，找到在第几轮获得最大收益已经最大收益
class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; if(n < 2) return 0; int maxT = n / 2; int INF = Integer.MIN_VALUE / 2; int[][] f = new int[maxT + 2][2]; // 全局初始化极小 for(int j = 0; j < maxT + 2; j++){ f[j][0] = INF; f[j][1] = INF; } f[0][0] = 0; for(int x : prices){ for(int j = maxT + 1; j > 0; j--){ f[j][0] = Math.max(f[j][0], f[j][1] + x); f[j][1] = Math.max(f[j - 1][0] - x, f[j][1]); } } // 取所有额度>=k对应的最优解 int ans = 0; for(int j = k + 1; j <= maxT + 1; j++){ ans = Math.max(ans, f[j][0]); } return ans; } }参考文献：灵神
