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天可能是买入/卖出状态所以需要增加一维来记录每天可能发生的情况。如果第i2天是卖出状态不持有股票 那么可能发生的情况是第i1天也不持有且没有买入操作第i天持有且卖出。如果第i2天是买入状态持有股票那么可能发生的情况是第i1天已经持有且没有卖出操作第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、手续费你可以无限次地完成交易但是你每笔交易都需要付手续费。如果你已经购买了一个股票在卖出它之前你就不能再继续购买股票了。迭代思路与上一个问题大致相同区别在于没有冷冻期所以第i1天的收益只与第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){ // 如果第i1天为不持有股票状态那么第i天如果也不持有二者收益相同如果持有那么就可以卖出获得收益同时要付出一定的手续费。 dp[i 1][0] Math.max(dp[i][0], dp[i][1] prices[i] - fee); // 如果第i1天为持有股票状态那么第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一共k1种次数状态数组第二维必须开到k1才能容纳全部次数为了不越界数组长度开到k2初始化为Integer.MIN_VALUE / 2的部分标记所有状态初始为「不可达非法状态」——在第 0 天无任何操作不存在任何买卖行为不管是持有股票、还是完成任意笔交易都无法实现全部置极小值。初始化为0的部分f[0][j][0] 0——还没处理任何一天i0视作已经完成 j 笔交易、且手上无股票利润为 0class 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]持有股票状态k1的初始时刻不可能持有股票持股状态标记为不可达极小值。初始化为0的部分k为偏移设计实际计算到k1所以k0标记为不可达。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[k1][0]是否为极小如果是说明小于k次就完成了交易不满足题意。//必须恰好k笔取f[k1][0]若还是极小说明凑不齐k笔返回0 int res f[k 1][0]; return res 0 ? 0 : res;变形至少k次完成1、根据prices数组判断是否可以至少完成k次交易至多可以完成几次交易maxT2、后续基于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; } }参考文献灵神