企业官网建设流程全解析

题目描述：

给定一个整数数组prices，其中第prices[i]表示第i天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入:prices = [1,2,3,0,2]输出:3解释:对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入:prices = [1]输出:0

解题思路：

方法一：动态规划

核心思路：状态机 DP

状态定义：

每天有三种状态：

• dp[i][0]：第 i 天持有股票的最大利润

• dp[i][1]：第 i 天不持有股票，处于冷冻期的最大利润

• dp[i][2]：第 i 天不持有股票，不处于冷冻期的最大利润

状态转移：

dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])

• 继续持有，或从"不持有不冷冻"状态买入

dp[i][1] = dp[i-1][0] + prices[i]

• 从"持有"状态卖出，进入冷冻期

dp[i][2] = max(dp[i-1][1], dp[i-1][2])

• 冷冻期结束，或继续不持有不冷冻

初始化：

dp[0][0] = -prices[0] // 买入 dp[0][1] = 0 // 不可能（第一天就冷冻） dp[0][2] = 0 // 不操作

具体过程示例：

prices = [1,2,3,0,2]

最大利润 = max(dp[4][1], dp[4][2]) = max(3, 2) = 3✅

代码实现：

写法1：二维 DP

class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0; vector<vector<int>> dp(n, vector<int>(3, 0)); dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0; for (int i = 1; i < n; i++) { dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]); dp[i][1] = dp[i-1][0] + prices[i]; dp[i][2] = max(dp[i-1][1], dp[i-1][2]); } return max(dp[n-1][1], dp[n-1][2]); } };

写法2：空间优化（滚动变量）

class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0; int hold = -prices[0]; // 持有股票 int cooldown = 0; // 冷冻期 int notHold = 0; // 不持有不冷冻 for (int i = 1; i < n; i++) { int newHold = max(hold, notHold - prices[i]); int newCooldown = hold + prices[i]; int newNotHold = max(cooldown, notHold); hold = newHold; cooldown = newCooldown; notHold = newNotHold; } return max(cooldown, notHold); } };

复杂度分析：

关键细节：

1. 为什么有三种状态？

因为冷冻期的存在，需要区分"不持有股票"的两种情况：

• 刚卖出，处于冷冻期（第二天不能买）

• 不处于冷冻期（可以买）

2. 为什么dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])？

• dp[i-1][0]：继续持有

• dp[i-1][2] - prices[i]：从"不持有不冷冻"状态买入

注意：不能从dp[i-1][1]（冷冻期）买入，因为冷冻期不能买。

3. 为什么dp[i][1] = dp[i-1][0] + prices[i]？

从"持有"状态卖出，进入冷冻期。

4. 为什么dp[i][2] = max(dp[i-1][1], dp[i-1][2])？

• dp[i-1][1]：冷冻期结束，变成"不持有不冷冻"

• dp[i-1][2]：继续"不持有不冷冻"

5. 和「买卖股票 II」的区别

方法二：记忆化搜索

代码实现：

class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); vector<vector<int>> memo(n, vector<int>(2, -1)); return dfs(prices, 0, 0, memo); // 0: 不持有, 1: 持有 } private: int dfs(vector<int>& prices, int i, int holding, vector<vector<int>>& memo) { if (i >= prices.size()) return 0; if (memo[i][holding] != -1) return memo[i][holding]; int result; if (holding) { // 持有：卖出（进入冷冻期）或继续持有 result = max(prices[i] + dfs(prices, i + 2, 0, memo), dfs(prices, i + 1, 1, memo)); } else { // 不持有：买入或继续不持有 result = max(-prices[i] + dfs(prices, i + 1, 1, memo), dfs(prices, i + 1, 0, memo)); } memo[i][holding] = result; return result; } };

复杂度：时间 O(n)，空间 O(n)

两种方法对比：

总结：