Javajava算法
动态规划：买卖股票最佳时机（含冷冻期与手续费）
本文讲解动态规划在股票买卖问题中的应用，涵盖最多 k 次交易、含冷冻期及含手续费三种场景。通过定义持有与不持有状态，推导状态转移方程，并给出 Java 代码实现。重点分析了状态初始化、遍历顺序及边界条件处理，帮助读者掌握此类 DP 问题的通用解法。
本文讲解动态规划在股票买卖问题中的应用，涵盖最多 k 次交易、含冷冻期及含手续费三种场景。通过定义持有与不持有状态，推导状态转移方程，并给出 Java 代码实现。重点分析了状态初始化、遍历顺序及边界条件处理，帮助读者掌握此类 DP 问题的通用解法。
这道题是'最多两次交易'的通用版（k 次），状态设计沿用'成对状态'的思路，用 dp[i][j] 表示第 i 天处于第 j 种状态时的最大现金。
以示例 k=2、prices = [3,3,5,0,0,3,1,4] 为例，最终第 7 天（i=7，价格 = 4）：dp[7][4] = 6。验证了代码的通用性。
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int len = prices.length;
// dp[i][j]：第 i 天处于第 j 种状态的最大现金
// j=0：无操作；j=1：第 1 次持有；j=2：第 1 次卖出；...；j=2m-1：第 m 次持有；j=2m：第 m 次卖出
int[][] dp = new int[len][2 * k + 1];
// 初始化第 0 天的状态：所有'第 m 次持有'状态初始为 -prices[0]，'卖出'状态默认 0
for (int i = 1; i <= k; i++) {
dp[0][2 * i - 1] = -prices[0];
}
// 外层循环：遍历每一天（从第 1 天开始，依赖前一天状态）
for (int i = 1; i < len; i++) {
// 内层循环：遍历每一次交易（从第 1 次到第 k 次）
for (int j = 1; j <= k; j++) {
// 计算第 j 次持有的最大现金
dp[i][2 * j - 1] = Math.max(dp[i-1][2 * j - 1], dp[i-1][2 * j - 2] - prices[i]);
// 计算第 j 次卖出的最大现金
dp[i][2 * j] = Math.max(dp[i-1][2 * j], dp[i-1][2 * j - 1] + prices[i]);
}
}
return dp[len - 1][2 * k];
}
}
需要细化状态以覆盖'冷冻期'约束，定义 dp[i][j] 为第 i 天处于状态 j 时的最大现金，其中 j 分为 3 种状态：
从第 1 天（i=1）遍历到最后一天（i=len-1），保证计算时前一天状态已确定。
以经典示例 prices = [1,2,3,0,2] 为例，最大利润为 3。逐天计算验证状态转移正确性。
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int len = prices.length;
// dp[i][0]：第 i 天持有股票的最大现金
// dp[i][1]：第 i 天不持有股票且处于冷冻期的最大现金
// dp[i][2]：第 i 天不持有股票且不处于冷冻期的最大现金
int[][] dp = new int[len][3];
// 初始化第 0 天的状态
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
// 遍历天数：从第 1 天到最后一天
for (int i = 1; i < len; i++) {
// 状态 0：持有股票
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2] - prices[i]);
// 状态 1：冷冻期
dp[i][1] = dp[i-1][0] + prices[i];
// 状态 2：非冷冻期且不持有
dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);
}
return Math.max(dp[len-1][1], dp[len-1][2]);
}
}
数组定义和'无限次交易'版本形式一致，但状态含义因手续费规则有细微调整：
从第 1 天（i=1）遍历到最后一天（i=len-1），保证计算 dp[i] 时 dp[i-1] 已确定。
以经典示例 prices = [1,3,2,8,4,9]、fee=2 为例，最大利润为 8。逐天计算验证。
class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices == null || prices.length <= 1) {
return 0;
}
int len = prices.length;
// dp[i][0]：第 i 天持有股票时的最大现金
// dp[i][1]：第 i 天不持有股票时的最大现金
int[][] dp = new int[len][2];
// 初始化第 0 天的状态
dp[0][0] = -prices[0];
dp[0][1] = 0;
// 遍历天数：从第 1 天到最后一天
for (int i = 1; i < len; i++) {
// 状态转移 1：第 i 天持有股票的最大现金
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
// 状态转移 2：第 i 天不持有股票的最大现金（核心差异：卖出扣手续费）
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
}
return dp[len - 1][1];
}
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online