题目给定一个整数数组prices其中第prices[i]表示第i天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。示例 1:输入:prices [1,2,3,0,2]输出:3解释:对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例 2:输入:prices [1]输出:0提供代码class Solution { public int maxProfit(int[] prices) { } }作答class Solution { public int maxProfit(int[] prices) { // 数组长度 int n prices.length; //当提供的股票价格小于等于1天则无法完成买入卖出 if(n 1) return 0; //dp0:买入 dp1:冷冻期 dp2:不持有、不冷冻 int dp0 -prices[0]; int dp1 0; int dp2 0; for(int i 1; i n; i){ int dp00 Math.max( dp0, dp2-prices[i]); int dp10 dp0 prices[i]; int dp20 Math.max( dp1, dp2); dp0 dp00; dp1 dp10; dp2 dp20; } return Math.max( dp1, dp2); } }思路核心dp Dynamic Programming即动态规划1由于数据是动态的没有固定规律所以需要明确第i天结束时股票的状态以及一共赚到的钱数。状态分为三种持有股票dp0未持有股票dp1和dp2.其中dp1是冷冻期dp2是非冷冻期。状态若为dp0持有股票金额昨天持有-今天价格买入即dp0-prices[i]如果是昨天就有则金额dp0.状态若为dp1未持有冷冻则金额昨天持有今天价格卖出dp0 prices[i].状态若为dp2未持有未冷冻会有两种情况。若昨天为冷冻期则金额dp1若昨天不是冷冻期则金额dp2.2 int dp0 -prices[0];的作用这是假设第一天就买入的情况下所赚金额。且dp0-prices[i]的情况保证了不会由于第一天买入过多带来的亏损。
