121. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
思路：
方法一：暴力方法。
方法二：针对暴力方法的优化。只需要关心之前（不包括现在）看到的最低股价，于是在遍历的过程中，记录下之前看到的最低股价，就可以省去内层循环。
方法三：动态规划。
1、设定状态
这道题其实是一个典型的二维 dp 问题。「动态规划」用于多阶段最优化问题的求解。这里天数代表每个阶段，即一天一天看，设置为第一维。为了消除后效性（前面的状态确定下来以后不会因为后面状态而更改），将当天是否持股设置为第二维的状态。于是：
状态 dp[i][j] 表示：在下标为 i 的这一天，用户手上持股状态为 j 所获得的最大利润。
说明：
j 只有 2 个值：0 表示不持股（特指卖出股票以后的不持股状态），1 表示持股。
「用户手上不持股」不代表用户一定在下标为 i 的这一天把股票抛售了；
2、思考状态转移方程
dp[i][0] 怎样转移？
dp[i - 1][0] ：当然可以从昨天不持股转移过来，表示从昨天到今天什么都不操作，这一点是显然的；
dp[i - 1][1] + prices[i]：昨天持股，就在下标为 i 的这一天，我卖出了股票，状态由 1 变成了 0，此时卖出股票，因此加上这一天的股价。
综上：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] 怎样转移？
dp[i - 1][1] ：昨天持股，今天什么都不操作，当然可以从昨天持股转移过来，这一点是显然的；
-prices[i]：注意：状态 1 不能由状态 0 来，因为事实上，状态 0 特指：「卖出股票以后不持有股票的状态」，请注意这个状态和「没有进行过任何一次交易的不持有股票的状态」的区别。
因此，-prices[i] 就表示，在下标为 i 的这一天，执行买入操作得到的收益。注意：因为题目只允许一次交易，因此不能加上 dp[i - 1][0]。
综上：dp[i][1] = max(dp[i - 1][1], -prices[i]);
3、考虑初始值
第 0 天不持股，显然 dp[0][0] = 0；
第 0 天持股，显然dp[0][1] = -prices[0]。
4、考虑输出
从状态转移方程可以看出，每一天的状态都考虑了之前的状态。在只发生一次交易的情况下，持有这支股票一定不能使我们获得最大利润。因此输出是 dp[len - 1][0]，不可能是持股的状态 dp[len - 1][1]，
class Solution {public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) {return 0;}int[][] dp = new int[len][2];dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < len; 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], -prices[i]);}return dp[len - 1][0];}}
5、考虑是否可以空间优化
由于 dp[i] 仅仅依赖于 dp[i - 1] ，因此，我们可以使用滚动数组的技巧进行空间优化。
122. 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路：
方法一：暴力搜索
利用回溯法，可以保持当前股票持有状态，也可以改变当前状态。
class Solution {private int res = 0;public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) {return 0;}dfs(prices, 0, len, 0, res);return res;}/*** @param prices 股价数组* @param index 当前是第几天，从 0 开始* @param len 数组长度* @param status 0 表示不持有股票，1表示持有股票，* @param profit 当前收益*/private void dfs(int[] prices, int index, int len, int status, int profit) {if (index == len) {res = Math.max(res, profit);return;}dfs(prices, index + 1, len, status, profit);if (status == 0) {dfs(prices, index + 1, len, 1, profit - prices[index]);} else {dfs(prices, index + 1, len, 0, profit + prices[index]);}}}
方法二：贪心算法
思路：
从第 i 天（这里 i >= 1）开始，与第 i - 1 的股价进行比较，如果股价有上升（严格上升），就将升高的股价（ prices[i] - prices[i- 1] ）记入总利润，按照这种算法，得到的结果就是符合题意的最大利润。
下面对这个算法进行几点说明：
1、该算法仅可以用于计算，但计算的过程并不是真正交易的过程，但可以用贪心算法计算题目要求的最大利润。下面说明这个等价性：以 [1, 2, 3, 4] 为例，这 4 天的股价依次上升，按照贪心算法，得到的最大利润是：
res = (prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])= prices[3] - prices[0]
仔细观察上面的式子，按照贪心算法，在索引为 1、2、3 的这三天，我们做的操作应该是买进昨天的，卖出今天的，虽然这种操作题目并不允许，但是它等价于：“在索引为 0 的那一天买入，在索引为 3 的那一天卖出”。
2、解释一下它为什么叫 “贪心算法”
我们还是回到贪心算法的定义：（下面是来自《算法导论（第三版）》第 16 章的叙述）
“贪心算法” 在每一步总是做出在当前看来最好的选择。
因此，
“贪心算法” 和 “动态规划”、“回溯搜索” 算法一样，完成一件事情，是分步决策的；
“贪心算法” 在每一步总是做出在当前看来最好的选择，我是这样理解 “最好” 这两个字的意思：
“最好” 的意思往往根据题目而来，可能是 “最小”，也可能是 “最大”；
贪心算法和动态规划相比，它既不看前面（也就是说它不需要从前面的状态转移过来），也不看后面（无后效性，后面的选择不会对前面的选择有影响），因此贪心算法时间复杂度一般是线性的，空间复杂度是常数级别的。
这道题 “贪心” 的地方在于，对于 “今天的股价 - 昨天的股价”，得到的结果有 3 种可能：（1）正数（2）0（3）负数。
贪心算法的决策是：只加正数。
class Solution {public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) {return 0;}int res = 0;for (int i = 0; i < len - 1; i++) {int diff = prices[i + 1] - prices[i];if (diff > 0) {res += diff;}}return res;}}
复杂度分析：
- 时间复杂度：O(N)，这里 N 表示股价数组的长度；
- 空间复杂度：O(1)。
状态 dp[i][j] 定义如下
方法三：动态规划
状态 dp[i][j] 定义如下
第一维 i 表示索引为 i 的那一天（具有前缀性质，即考虑了之前天数的收益）能获得的最大利润；
第二维 j 表示索引为 i 的那一天是持有股票，还是持有现金。这里 0 表示持有现金（cash），1 表示持有股票（stock）。
class Solution {public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) {return 0;}// 0：持有现金// 1：持有股票int[][] dp = new int[len][2];dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < len; 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]);}return dp[len - 1][0];}}
123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路：
方法一：暴力搜索
利用回溯法，总体上和上一题类似，增加交易次数小于等于 2 的判断。
class Solution {
private int res;
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
dfs(prices, 0, 0, len, 0, 0);
return res;
}
// status, 0：持有现金，1：持有股票
private void dfs(int[] prices, int count, int index, int len, int status, int profit) {
if (count == 2 || index == len) {
res = Math.max(res, profit);
return;
}
dfs(prices, count, index+1, len, status, profit);
if (status == 0) {
dfs(prices, count, index+1, len, 1, profit - prices[index]);
} else {
dfs(prices, count+1, index+1, len, 0, profit + prices[index]);
}
}
}
方法二：动态规划
第 1 步：状态定义
状态定义：dp[i][j] 表示在 [0, i] 区间里（这个状态依然是前缀性质的），状态为 j 的最大收益。j 的含义如下：
j = 0：还未开始交易；
j = 1：第 1 次买入一支股票；
j = 2：第 1 次卖出一支股票；
j = 3：第 2 次买入一支股票；
j = 4：第 2 次卖出一支股票。
第 2 步：状态转移方程
“状态转移方程”可以用下面的图表示，它的特点是：状态要么停留，要么向后面走，状态不能回退。
第 3 步：思考初始化
第 0 天的时候很容易初始化前两个状态，而状态 3 （表示第 2 次持股）只能赋值为一个不可能的数。
注意：只有在之前的状态有被赋值的时候，才可能有当前状态。
第 4 步：思考输出
最后一天不持股的状态都可能成为候选的最大利润。
第 5 步： 思考状态压缩
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
// dp[i][j] ，表示 [0, i] 区间里，状态为 j 的最大收益
// j = 0：什么都不操作
// j = 1：第 1 次买入一支股票
// j = 2：第 1 次卖出一支股票
// j = 3：第 2 次买入一支股票
// j = 4：第 2 次卖出一支股票
// 初始化
int[][] dp = new int[len][5];
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 3 状态都还没有发生，因此应该赋值为一个不可能的数
for (int i = 0; i < len; i++) {
dp[i][3] = Integer.MIN_VALUE;
}
// 状态转移只有 2 种情况：
// 情况 1：什么都不做
// 情况 2：由上一个状态转移过来
for (int i = 1; i < len; i++) {
// j = 0 的值永远是 0
dp[i][0] = 0;
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
// 最大值只发生在不持股的时候，因此来源有 3 个：j = 0 ,j = 2, j = 4
return Math.max(0, Math.max(dp[len - 1][2], dp[len - 1][4]));
}
}
188. 买卖股票的最佳时机 IV
309. 最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
思路：
这道题增加了冷冻期这样一个条件，也没有限制多少笔交易。因此只需要增加一个状态（表示当前这一天处在「冷冻期」）即可。注意：这里是增加一个状态，不是增加一维状态。
第 1 步：状态定义
dp[i][j] 表示 [0, i] 区间内，在下标为 i 这一天状态为 j 时的最大收益。
这里 j 取三个值：
dp[i][j] 表示 [0, i] 区间内，在下标为 i 这一天状态为 j 时的最大收益。
第一种取法：
0 表示不持股；
1 表示持股；
2 表示处在冷冻期。
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][2] - prices[i]);
dp[i][2] = dp[i - 1][0];
第二种取法：
不持股且能购买(0)->持股(1)->不持股且不能购买(2)
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
dp[i][2]=dp[i-1][1]+prices[i];
第 2 步：状态转移方程
对于第一种取法：
不持股可以由这两个状态转换而来：
- 昨天不持股，今天什么都不操作，仍然不持股；
- 昨天持股，今天卖了一股。
持股可以由这两个状态转换而来：
- 昨天持股，今天什么都不操作，仍然持股；
- 昨天处在冷冻期，今天买了一股；
处在冷冻期只可以由不持股转换而来，因为题目中说，刚刚把股票卖了，需要冷冻 1 天。
对于第二种取法：
不持股且能购买：
- 昨天不持股，今天什么都不操作，仍然不持股；
- 昨天处在冷冻期，不持股且不能购买。
持股：
- 昨天持股，今天什么都不操作，仍然持股；
- 昨天处在不持股且能购买，然后买了一股。
不持股且不能购买：昨天把持有的股票卖了，今天为冷冻期。
第 3 步：思考初始化
在第 0 天，不持股的初始化值为 0，持股的初始化值为 -prices[0]（表示购买了一股），虽然不处于冷冻期，但是初始化的值可以为 0。
第 4 步：思考输出
每一天都由前面几天的状态转换而来，最优值在最后一天。取不持股和冷冻期的最大者。
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
// 0：持有现金，1：持有股票，2：还在冷冻期
int[][] dp = new int[len][3];
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for (int i = 1; i < len; 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][2] - prices[i]);
dp[i][2] = dp[i - 1][0];
}
return dp[len - 1][0];
}
}
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
// 不持股且能购买(0)->持股(1)->不持股且不能购买(2)
int[][] dp = new int[len][3];
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = dp[i - 1][1] + prices[i];
}
return Math.max(dp[len - 1][0], dp[len - 1][2]);
}
}
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
思路：
总体和之前的题目类似，多考虑一个手续费就行。手续费对状态转移方程的结构没有影响。
class Solution {
public int maxProfit(int[] prices, int fee) {
int len = prices.length;
if (len < 2) {
return 0;
}
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[len - 1][0];
}
}
若有收获，就点个赞吧
0 人点赞
