188. 买卖股票的最佳时机 IV
- 原题链接:
- 完成情况:
- 解题思路:
- 代码解释
- 类级变量与初始化
- 动态规划初始化
- 递归函数 `dfs_maxProfit`
- `Integer.MIN_VALUE / 5` 的作用
- 总结
- 参考代码:
- _188买卖股票的最佳时机IV
- 错误经验吸取
原题链接:
188. 买卖股票的最佳时机 IV
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
完成情况:
解题思路:
代码解释
该代码实现了一个算法来计算在股票价格数组 prices
中最多进行 k
笔交易所能获得的最大利润。以下是对代码的详细解释:
类级变量与初始化
class Solution {private int[] prices;private int[][][] dp_maxProfit;public int maxProfit(int k, int[] prices) {this.prices = prices;int n = prices.length;dp_maxProfit = new int[n][k + 1][2];for (int i = 0; i < n; i++) {for (int j = 0; j <= k; j++) {Arrays.fill(dp_maxProfit[i][j], -1);}}return dfs_maxProfit(n - 1, k, 0);}
prices
:存储股票价格数组。dp_maxProfit
:一个三维数组,保存到第n
天进行了t
次交易并且是否持有股票的最大利润。数组的维度为[n][k+1][2]
,其中:n
:表示天数。k+1
:表示交易次数(包括 0 次交易)。2
:表示是否持有股票(0
表示不持有,1
表示持有)。
动态规划初始化
for (int i = 0; i < n; i++) {for (int j = 0; j <= k; j++) {Arrays.fill(dp_maxProfit[i][j], -1);}}
- 使用
Arrays.fill
方法将dp_maxProfit
三维数组的所有元素初始化为-1
,表示这些状态尚未计算。
递归函数 dfs_maxProfit
private int dfs_maxProfit(int n, int t, int visited) {if (t < 0) return Integer.MIN_VALUE / 5; // 防止溢出if (n < 0) return visited == 1 ? Integer.MIN_VALUE / 5 : 0;if (dp_maxProfit[n][t][visited] != -1) return dp_maxProfit[n][t][visited];if (visited == 1) {return dp_maxProfit[n][t][visited] = Math.max(dfs_maxProfit(n - 1, t, 1), dfs_maxProfit(n - 1, t - 1, 0) - prices[n]);}return dp_maxProfit[n][t][visited] = Math.max(dfs_maxProfit(n - 1, t, 0), dfs_maxProfit(n - 1, t, 1) + prices[n]);}
}
-
dfs_maxProfit(n, t, visited)
:递归函数,用于计算到第n
天进行了t
次交易并且是否持有股票的最大利润。- 如果
t < 0
:返回一个极小值Integer.MIN_VALUE / 5
。这用于防止溢出并确保不可能的状态不会影响结果。 - 如果
n < 0
:当天数已经小于 0,检查是否持有股票。如果持有股票,返回一个极小值Integer.MIN_VALUE / 5
。否则返回0
,表示没有任何交易利润。 - 如果
dp_maxProfit[n][t][visited] != -1
:直接返回预计算的结果,避免重复计算。
- 如果
-
递归逻辑:
- 如果
visited == 1
(当前持有股票),选择两种状态中的最大值:- 保持持有股票状态:
dfs_maxProfit(n - 1, t, 1)
- 卖出股票:
dfs_maxProfit(n - 1, t - 1, 0) - prices[n]
- 保持持有股票状态:
- 如果
visited == 0
(当前不持有股票),选择两种状态中的最大值:- 保持不持有股票状态:
dfs_maxProfit(n - 1, t, 0)
- 买入股票:
dfs_maxProfit(n - 1, t, 1) + prices[n]
- 保持不持有股票状态:
- 如果
Integer.MIN_VALUE / 5
的作用
return Integer.MIN_VALUE / 5; // 防止溢出
该语句用于在递归过程中避免溢出。具体原因如下:
Integer.MIN_VALUE
是 Java 中整数的最小值,即-2^31
。如果直接使用Integer.MIN_VALUE
作为返回值,在某些计算中可能会导致溢出,变成正数。- 将
Integer.MIN_VALUE
除以 5,仍然是一个很小的负数,但不至于达到溢出风险。这样可以确保逻辑处理时不会因为极值导致错误。
总结
这段代码使用了动态规划和递归相结合的方法,通过三维数组 dp_maxProfit
来记录不同状态下的最大利润,避免了重复计算,确保在最多进行 k
次交易的情况下,能计算出最大可能利润。
参考代码:
_188买卖股票的最佳时机IV
package leetcode板块;import java.util.Arrays;public class _188买卖股票的最佳时机IV {private int [] prices;private int [][][] dp_maxProfit; // 扩大维度/**** @param k* @param prices* @return*/public int maxProfit(int k, int[] prices) {//设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。// TODO 类似于刚才的 -> 123买卖股票的最佳时机III ??? 构造k维数组,去求dp的K,k与k+1之间通过迭代去计算k维的利润集合。this.prices = prices;int n = prices.length;dp_maxProfit = new int[n][k+1][2]; // n个数组值 ,k+1去记录作为第几笔交易的"最大利润" ,2用于去记录当前操作下是否访问过该号位元素for (int i = 0;i<n;i++){for (int j = 0;j<=k;++j){Arrays.fill(dp_maxProfit[i][j],-1); //memories[i][j]的下一级全部标为 -1}}return dfs_maxProfit(n-1,k,0);}/**** @param n :numbers* @param t :transaction* @param visited* @return*/private int dfs_maxProfit(int n, int t, int visited) {if (t < 0) return Integer.MIN_VALUE / 5; // 防止溢出if (n < 0) return visited == 1 ? Integer.MIN_VALUE / 5 : 0;if (dp_maxProfit[n][t][visited] != -1) return dp_maxProfit[n][t][visited];if (visited == 1){return dp_maxProfit[n][t][visited] = Math.max(dfs_maxProfit(n-1,t,1),dfs_maxProfit(n-1,t-1,0) - prices[n]);}return dp_maxProfit[n][t][visited] = Math.max(dfs_maxProfit(n-1,t,0),dfs_maxProfit(n-1,t,1)+prices[n]);}