冷冻期股票交易：动态规划解法

LeetCode309给定一个整数数组prices其中第prices[i]表示第i天的股票价格 。​设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。示例 1:输入:prices [1,2,3,0,2]输出:3解释:对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]Python解法动态规划class Solution: def maxProfit(self, prices: List[int]) - int: if not prices: return 0 n len(prices) f [[0] * 3 for _ in range(n)] f[0][0] -prices[0] f[0][1] 0 f[0][2] 0 for i in range(1, n): f[i][0] max(f[i - 1][0], f[i - 1][2] - prices[i]) f[i][1] f[i - 1][0] prices[i] f[i][2] max(f[i - 1][1], f[i - 1][2]) return max(f[n - 1][1], f[n - 1][2])解释状态f[i][0]第 i 天持有股票f[i][1]第 i 天刚卖出进入冷冻期f[i][2]第 i 天空仓、不在冷冻期状态流转逻辑持有股票 (0)要么之前就拿着要么今天买入前一天必须是非冷冻空仓 2冷冻期 (1)只能今天卖出前一天一定持股 (0)非冷冻空仓 (2)昨天冷冻期今天解冻或一直空仓不可能从持股直接变来必须隔一天冷冻Java解法动态规划class Solution { public int maxProfit(int[] prices) { if(prices.length 0)return 0; int n prices.length; int[][] f new int[n][3]; f[0][0] -prices[0]; f[0][1] 0; f[0][2] 0; for(int i 1; i n; i){ f[i][0] Math.max(f[i - 1][0], f[i - 1][2] - prices[i]); f[i][1] f[i - 1][0] prices[i]; f[i][2] Math.max(f[i - 1][1], f[i - 1][2]); } return Math.max(f[n - 1][1], f[n - 1][2]); } }C解法动态规划class Solution { public: int maxProfit(vectorint prices) { if (prices.empty()) return 0; int n prices.size(); // dp[i][0]持有股票 dp[i][1]冷冻期 dp[i][2]非冷冻空仓 vectorvectorint dp(n, vectorint(3, 0)); dp[0][0] -prices[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.back()[1], dp.back()[2]); } };