核心思想

动态规划方法的复杂度大致可以理解为：O (状态数量 * 每个状态的枚举代价) 当每个状态的枚举代价为O (1)，那么写出记忆化搜索的版本，就是时间复杂度最好的实现了但是当每个状态的枚举代价比较高的时候，记忆化搜索的版本可能不是最优解，可能存在进一步的优化之所以从记忆化搜索改出了严格位置依赖的版本，是为了建立空间感，让观察并优化枚举的分析变容易

通过观察优化枚举的技巧包括： 观察并优化转移方程（本章节，下一章节）、观察并设计高效的查询结构（下章节）

本节课的题目4、题目7，是最能体现观察并优化转移方程技巧的题目 但题目4属于著名的买卖股票系列问题中的一个，所以索性把这个系列全写了，请重点关注题目4、题目7

例题

1、买卖股票的最佳时机

题目描述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 104

代码如下

 package main.java.class082;  
   
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code01_Stock  
  * @description: 买卖股票的最佳时机  
  * // 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格  
  * // 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票  
  * // 设计一个算法来计算你所能获取的最大利润  
  * // 返回你可以从这笔交易中获取的最大利润  
  * // 如果你不能获取任何利润，返回 0  
  * // 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/  
  * @author: zs宝  
  * @create: 2025-10-01 11:59  
  * @Version 1.0  
  **/public class Code01_Stock {  
     class Solution {  
         public int maxProfit(int[] prices) {  
             int ans=0;  
             for(int i=1,min=prices[0];i<prices.length;i++){  
                 ans=Math.max(ans,prices[i]-min);  
                 min=Math.min(min,prices[i]);  
             }  
             return ans;  
         }  
     }  
 }

2、买卖股票的最佳时机 II

题目描述：给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。

返回 你能获得的 最大利润。

示例 1：

输入：prices = [7,1,5,3,6,4] 输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。最大总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。最大总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

提示：

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

代码如下

 package main.java.class082;  
   
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code02_Stock2  
  * @description: 买卖股票的最佳时机 II  
  * // 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格  
  * // 在每一天，你可以决定是否购买和/或出售股票  
  * // 你在任何时候 最多 只能持有 一股 股票  
  * // 你也可以先购买，然后在 同一天 出售  
  * // 返回 你能获得的 最大 利润  
  * // 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/  
  * @author: zs宝  
  * @create: 2025-10-01 12:05  
  * @Version 1.0  
  **/public class Code02_Stock2 {  
     class Solution {  
         public int maxProfit(int[] prices) {  
             int ans=0;  
             for(int i=1;i<prices.length;i++){  
                 if(prices[i]>prices[i-1]){  
                     ans+=(prices[i]-prices[i-1]);  
                 }  
             }  
             return ans;  
         }  
     }  
 }

3、买卖股票的最佳时机 III

题目描述：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

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

示例 1:

输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

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

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 105

解题思路：

dp1[i]:在前i次进行第一次交易收益为多少
dp2[i]:在0-i次发生2次交易。并且第二次交易在i时刻卖出，最大利润多少。那么在求解时就需要枚举出第二次交易的起始点位置
通过观察优化枚举时间 dp2[i]=Math.max(dp2[i],dp1[j]+prices[i]-prices[j]); ->dp2[i]=Math.max(dp1[j]-prices[j])+prices[i]

项目名称	内容填写（每道题一行填写）
📘 题目编号 / 标题	LeetCode 123 + 买卖股票的最佳时机Ⅲ
🧠 题目关键词（原文关键词）	最多可以完成两笔交易，必须在再次购买前出售掉之前的股票。
🧩 抽象问题类型（题目本质）	最大利润模型
🔍 数据规模 / 限制	- `1 <= prices.length <= 105` - `0 <= prices[i] <= 105`
🧭 我的初步思路	动态规划
✅ 正确解法类型	动态规划
❗ 没想到的原因	dp2的定义最开始没有想出来
📦 归入的题型分类	动态规划类
🧠 触发词（以后遇到就联想）	股票买卖2次交易->动态规划
🧪 解法一句话总结	分别定义一次与二次交易的dp数组，第二次交易要枚举第二次交易的起始位置，并通过观察优化枚举时间

代码如下：

 package main.java.class082;  
   
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code03_Stock3  
  * @description:买卖股票的最佳时机 III  
  * // 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。  
  * // 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易  
  * // 注意：你不能同时参与多笔交易，你必须在再次购买前出售掉之前的股票  
  * // 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii  
  * @author: zs宝  
  * @create: 2025-10-01 12:10  
  * @Version 1.0  
  **/public class Code03_Stock3 {  
     class Solution {  
         public int maxProfit(int[] prices) {  
             return maxProfit4(prices);  
         }  
   
         /**  
          思路正确：但是超时  
          */  
         public int maxProfit1(int[] prices) {  
             int n=prices.length;  
             //第一次交易可以带来的收益  
             //dp1[i]:在前i次进行第一次交易收益为多少  
             int[]dp1=new int[n];  
             for(int i=1,min=prices[0];i<n;i++){  
                 min=Math.min(min,prices[i]);  
                 dp1[i]=Math.max(dp1[i-1],prices[i]-min);  
             }  
             //第二次交易的收益  
             //dp2[i]:在0-i次发生2次交易。并且第二次交易在i时刻卖出，最大利润多少  
             int[]dp2=new int[n];  
             int ans=0;  
             for(int i=0;i<n;i++){  
                 //枚举第二次交易的起始位置  
                 for(int j=0;j<=i;j++){  
                     dp2[i]=Math.max(dp2[i],dp1[j]+prices[i]-prices[j]);  
                 }  
                 ans=Math.max(ans,dp2[i]);  
             }  
             return ans;  
         }  
   
         /**  
          通过观察法优化枚举时间  
          */  
         public int maxProfit2(int[] prices) {  
             int n=prices.length;  
             //第一次交易可以带来的收益  
             //dp1[i]:在前i次进行第一次交易收益为多少  
             int[]dp1=new int[n];  
             for(int i=1,min=prices[0];i<n;i++){  
                 min=Math.min(min,prices[i]);  
                 dp1[i]=Math.max(dp1[i-1],prices[i]-min);  
             }  
             //优化第二个dp2的枚举  
             //dp2[i]=Math.max(dp2[i],dp1[j]+prices[i]-prices[j]);  
             //dp2[i]=Math.max(dp1[j]-prices[j])+prices[i]            int[]best=new int[n];  
             best[0] = dp1[0] - prices[0];  
             for(int i=1;i<n;i++){  
                 best[i]=Math.max(best[i-1],dp1[i]-prices[i]);  
             }  
             //第二次交易的收益  
             //dp2[i]:在0-i次发生2次交易。并且第二次交易在i时刻卖出，最大利润多少  
             int[]dp2=new int[n];  
             int ans=0;  
             for(int i=0;i<n;i++){  
                 //枚举第二次交易的起始位置  
                 // for(int j=0;j<=i;j++){  
                 //     dp2[i]=Math.max(dp2[i],dp1[j]+prices[i]-prices[j]);                // }                //通过观察法优化枚举时间  
                 dp2[i]=best[i]+prices[i];  
                 ans=Math.max(ans,dp2[i]);  
             }  
             return ans;  
         }  
   
   
         /**  
          通过观察法优化枚举时间，进一步的优化  
          */  
         public int maxProfit3(int[] prices) {  
             int n=prices.length;  
             //第一次交易可以带来的收益  
             //dp1[i]:在前i次进行第一次交易收益为多少  
             int[]dp1=new int[n];  
             //优化第二个dp2的枚举  
             //dp2[i]=Math.max(dp2[i],dp1[j]+prices[i]-prices[j]);  
             //dp2[i]=Math.max(dp1[j]-prices[j])+prices[i]            int[]best=new int[n];  
             best[0] = dp1[0] - prices[0];  
             //第二次交易的收益  
             //dp2[i]:在0-i次发生2次交易。并且第二次交易在i时刻卖出，最大利润多少  
             int[]dp2=new int[n];  
             int ans=0;  
             for(int i=1,min=prices[0];i<n;i++){  
                 min=Math.min(min,prices[i]);  
                 dp1[i]=Math.max(dp1[i-1],prices[i]-min);  
                 best[i]=Math.max(best[i-1],dp1[i]-prices[i]);  
                 //枚举第二次交易的起始位置  
                 // for(int j=0;j<=i;j++){  
                 //     dp2[i]=Math.max(dp2[i],dp1[j]+prices[i]-prices[j]);                // }                //通过观察法优化枚举时间  
                 dp2[i]=best[i]+prices[i];  
                 ans=Math.max(ans,dp2[i]);  
             }  
             return ans;  
         }  
   
         /**  
          通过观察法优化枚举时间，进一步的优化+空间压缩  
          */  
         public int maxProfit4(int[] prices) {  
             int n=prices.length;  
             //第一次交易可以带来的收益  
             //dp1[i]:在前i次进行第一次交易收益为多少  
             int dp1=0;  
             //优化第二个dp2的枚举  
             //dp2[i]=Math.max(dp2[i],dp1[j]+prices[i]-prices[j]);  
             //dp2[i]=Math.max(dp1[j]-prices[j])+prices[i]            int best = dp1 - prices[0];  
             //第二次交易的收益  
             //dp2[i]:在0-i次发生2次交易。并且第二次交易在i时刻卖出，最大利润多少  
             int dp2=best+prices[0];  
             int ans=0;  
             for(int i=1,min=prices[0],temp;i<n;i++){  
                 min=Math.min(min,prices[i]);  
                 dp1=Math.max(dp1,prices[i]-min);  
                 best=Math.max(best,dp1-prices[i]);  
                 //枚举第二次交易的起始位置  
                 // for(int j=0;j<=i;j++){  
                 //     dp2[i]=Math.max(dp2[i],dp1[j]+prices[i]-prices[j]);                // }                //通过观察法优化枚举时间  
                 dp2=best+prices[i];  
                 ans=Math.max(ans,dp2);  
             }  
             return ans;  
         }  
     }  
   
 }

4、买卖股票的最佳时机 IV

题目描述：给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

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

示例 1：

输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3] 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000

解题思路：

这里有一个剪枝，就是数组长度为n那么这里面的数字的连线，最多有n/2个上坡，如果k>=n/2，那么问题就会变成第2个例题2、[买卖股票的最佳时机 II](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/)
定义 dp[i][j] 为在前j个时间中完成了i次交易
- 没有在j时完成第i次交易
- 在第j时完成第i次交易
  - 枚举第j次交易的起始时间
自己做的时候dp数组定义正确了，分类讨论也正确了，但是却错在记忆化搜索是自顶向下的调用，我当时写成自底向上f1(prices,k, 1,0,dp), 还在向当到达i== k时的baseline该如何跳出递归。真改给自己两巴掌
后续的优化枚举是由于发现严格依赖位置的动态规划版本有 dp[i][j]=Math.max(dp[i][j],prices[j]-prices[p]+dp[i-1][p]); ,刚好可以改写出来一个 dp[i-1][p]-prices[p] +prices[j]的内容，优化就从这里而来

项目名称	内容填写（每道题一行填写）
📘 题目编号 / 标题	LeetCode 188 + 买卖股票的最佳时机 IV
🧠 题目关键词（原文关键词）	整数数组 `prices` 和一个整数 `k`，最多可以完成 `k` 笔交易，不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
🧩 抽象问题类型（题目本质）	最大利润
🔍 数据规模 / 限制	- `1 <= k <= 100` - `1 <= prices.length <= 1000` - `0 <= prices[i] <= 1000`
🧭 我的初步思路	动态规划
✅ 正确解法类型	动态规划
❗ 没想到的原因	递归调用baseline想错了
📦 归入的题型分类	动态规划
🧠 触发词（以后遇到就联想）	买卖股票的最佳时机 IV+最多K次交易->动态规划
🧪 解法一句话总结	用一句话总结这道题的核心思路和转化方法

代码如下：

 package main.java.class082;  
   
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code04_Stock4  
  * @description: 买卖股票的最佳时机 IV  
  * // 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格  
  * // 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易  
  * // 也就是说，你最多可以买 k 次，卖 k 次  
  * // 注意：你不能同时参与多笔交易，你必须在再次购买前出售掉之前的股票  
  * // 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/  
  * @author: zs宝  
  * @create: 2025-10-02 09:31  
  * @Version 1.0  
  **/public class Code04_Stock4 {  
     class Solution {  
         public int maxProfit(int k, int[] prices) {  
             return maxProfit4(k,prices);  
         }  
   
   
         //记忆化搜索版本  
         public int maxProfit1(int k, int[] prices) {  
             int n=prices.length;  
             //如果k大于n/2,那么所有的上升都要算上  
             if(k>=(n/2)){  
                 return free(prices);  
             }  
   
             //如果不大于n/2,那么就是本题考虑的重点  
             //dp[i][j]:在前j个时间中完成了i次交易  
             int[][]dp=new int[k+1][n];  
             for(int i=0;i<=k;i++){  
                 Arrays.fill(dp[i],-1);  
             }  
             return f1(prices,k,k,n-1,dp);  
         }  
   
         public int free(int[]prices){  
             int ans=0;  
             for(int i=1;i<prices.length;i++){  
                 if(prices[i]>prices[i-1]){  
                     ans+=(prices[i]-prices[i-1]);  
                 }  
             }  
             return ans;  
         }  
   
         public int f1(int[]prices,int k,int i,int j,int[][]dp){  
             if(i==0){  
                 return 0;  
             }  
             if(j<=0){  
                 return 0;  
             }  
   
             if(dp[i][j]!=-1){  
                 return dp[i][j];  
             }  
             int ans=0;  
             //若在j位置前就完成了i次交易  
             ans=f1(prices,k,i,j-1,dp);  
             //若在j时完成了i次交易，枚举第i次交易的起始  
             for(int m=0;m<j;m++){  
                 ans=Math.max(ans,prices[j]-prices[m]+f1(prices,k,i-1,m,dp));  
             }  
             dp[i][j]=ans;  
             return ans;  
         }  
   
         //严格按照位置依赖的动态规划  
         public int maxProfit2(int k, int[] prices) {  
             int n=prices.length;  
             //如果k大于n/2,那么所有的上升都要算上  
             if(k>=(n/2)){  
                 return free(prices);  
             }  
   
             //如果不大于n/2,那么就是本题考虑的重点  
             //dp[i][j]:在前j个时间中完成了i次交易  
             int[][]dp=new int[k+1][n];  
             for(int i=1;i<=k;i++){  
                 for(int j=1;j<n;j++){  
                     dp[i][j]=dp[i][j-1];  
                     for(int p=0;p<j;p++){  
                         dp[i][j]=Math.max(dp[i][j],prices[j]-prices[p]+dp[i-1][p]);  
                     }  
                 }  
             }  
             return dp[k][n-1];  
         }  
   
   
   
         //严格按照位置依赖的动态规划+用观察法优化枚举行为  
         public int maxProfit3(int k, int[] prices) {  
             int n=prices.length;  
             //如果k大于n/2,那么所有的上升都要算上  
             if(k>=(n/2)){  
                 return free(prices);  
             }  
   
             //如果不大于n/2,那么就是本题考虑的重点  
             //dp[i][j]:在前j个时间中完成了i次交易  
             int[][]dp=new int[k+1][n];  
             for(int i=1,best;i<=k;i++){  
                 best=dp[i-1][0]-prices[0];  
                 for(int j=1;j<n;j++){  
                     dp[i][j]=Math.max(dp[i][j-1],best+prices[j]);  
                     best=Math.max(best,dp[i-1][j]-prices[j]);  
                 }  
             }  
             return dp[k][n-1];  
         }  
   
         //严格按照位置依赖的动态规划+用观察法优化枚举行为+空间压缩  
         public int maxProfit4(int k, int[] prices) {  
             int n=prices.length;  
             //如果k大于n/2,那么所有的上升都要算上  
             if(k>=(n/2)){  
                 return free(prices);  
             }  
   
             //如果不大于n/2,那么就是本题考虑的重点  
             //dp[i][j]:在前j个时间中完成了i次交易  
             int[]dp=new int[n];  
             for(int i=1,best,temp;i<=k;i++){  
                 best=dp[0]-prices[0];  
                 for(int j=1;j<n;j++){  
                     temp=dp[j];  
                     dp[j]=Math.max(dp[j-1],best+prices[j]);  
                     best=Math.max(best,temp-prices[j]);  
                 }  
             }  
             return dp[n-1];  
         }  
     }  
 }

5、买卖股票的最佳时机含手续费

题目描述：给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3 输出：6

提示：

1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104

解题思路

这是一个「无限次交易 + 每笔交易需要手续费」的股票买卖问题。
本质：每天都有两种状态 —— 持有股票 和 不持有股票。
状态定义
- prepare：持有股票时的最大利润（买入时需要减去股票价格和手续费）。
- done：不持有股票时的最大利润。
用动态规划维护「持有股票」和「不持有股票」两种状态，每天更新，最终得到最大利润。

项目名称	内容填写（每道题一行填写）
📘 题目编号 / 标题	LeetCode 714 + 买卖股票的最佳时机含手续
🧠 题目关键词（原文关键词）	整数数组 `prices`，其中 `prices[i]` 表示第 `i` 天的股票价格；整数 `fee` 代表了交易股票的手续费用，无限次地完成交易，每笔交易都需要付手续费
🧩 抽象问题类型（题目本质）	「无限次交易 + 每笔交易需要手续费」的股票买卖问题
🔍 数据规模 / 限制	- `1 <= prices.length <= 5 * 104` - `1 <= prices[i] < 5 * 104` - `0 <= fee < 5 * 104`
🧭 我的初步思路	动态规划
✅ 正确解法类型	动态规划
❗ 没想到的原因	没想到这怎么定义
📦 归入的题型分类	动态规划
🧠 触发词（以后遇到就联想）	「无限次交易 + 每笔交易需要手续费」的股票买卖问题->动态规划
🧪 解法一句话总结	用动态规划维护「持有股票」和「不持有股票」两种状态，每天更新，最终得到最大利润

代码如下

 package main.java.class082;  
   
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code05_Stack5  
  * @description: 买卖股票的最佳时机含手续费  
  * // 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格  
  * // 整数 fee 代表了交易股票的手续费用  
  * // 你可以无限次地完成交易，但是你每笔交易都需要付手续费  
  * // 如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。  
  * // 返回获得利润的最大值  
  * // 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费  
  * // 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/  
  * @author: zs宝  
  * @create: 2025-10-02 10:57  
  * @Version 1.0  
  **/public class Code05_Stack5 {  
     class Solution {  
         public int maxProfit(int[] prices, int fee) {  
             //在无限次交易的情况下，最后一次交易购入时的收益，持有股票时的收益  
             //因为买入股票要花钱，还要扣手续费，所以初始值是 -prices[0] - fee。  
             int prepare=-prices[0]-fee;  
   
             //在无限次交易时，最后一次交易完成时的收益,即表示「不持有股票」时的最大利润。  
             //初始值为 0，因为刚开始还没交易  
             int done=0;  
             for(int i=1;i<prices.length;i++){  
                 //第i时刻，要么完成交易，要么不完成  
                 //如果我今天把手里的股票卖了或者不卖  
                 done=Math.max(done,prepare+prices[i]);  
                 //第i时刻，要么开启交易，要么不开启  
                 //如果我今天买入股票，需要花掉当前价格和手续费;或者不买股票  
                 prepare=Math.max(prepare,done-prices[i]-fee);  
             }  
             return done;  
         }  
     }  
 }

6、卖股票的最佳时机含冷冻期

题目描述：给定一个整数数组prices，其中第 prices[i] 表示第 _i_ 天的股票价格。

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

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

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

示例 1:

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

示例 2:

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

提示：

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

解题思路：

这个题与上面第5个题类似5、[买卖股票的最佳时机含手续费](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)，但是这个题变成了有冷冻期
不知道如何下手，但是却忘记了分析状态，很多题都是在想办法表述一个题目描述的状态进行入手，这个题与第5题的撞他i几乎类似，只是交易多个了冷冻期，状态转移时考虑也只影响购买，不影响出售

项目名称	内容填写（每道题一行填写）
📘 题目编号 / 标题	LeetCode 309 + 买卖股票的最佳时机含冷冻期
🧠 题目关键词（原文关键词）	整数数组 `prices`，卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天
🧩 抽象问题类型（题目本质）	股票利润模型
🔍 数据规模 / 限制	- `1 <= prices.length <= 5000` - `0 <= prices[i] <= 1000`
🧭 我的初步思路	动态规划
✅ 正确解法类型	动态规划
❗ 没想到的原因	状态没想到如何表述
📦 归入的题型分类	动态规划类诶
🧠 触发词（以后遇到就联想）	买卖股票冷冻期->动态规划
🧪 解法一句话总结	用动态规划维护「持有股票」和「不持有股票」两种状态，每天更新，在更新持有股票时考虑冷冻期时间，最终得到最大利润

代码如下

 package main.java.class082;  
   
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code06_Stack6  
  * @description: 买卖股票的最佳时机含冷冻期  
  * // 给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格  
  * // 设计一个算法计算出最大利润  
  * // 在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:  
  * // 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)  
  * // 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）  
  * // 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/  
  * @author: zs宝  
  * @create: 2025-10-02 11:30  
  * @Version 1.0  
  **/public class Code06_Stack6 {  
     class Solution {  
         public int maxProfit(int[] prices) {  
             return maxProfit2(prices);  
         }  
         public int maxProfit1(int[] prices) {  
             int n = prices.length;  
             if (n < 2) {  
                 return 0;  
             }  
             //prepare[i]:无限次购买的情况下，在0-i时间内最后一次购买所剩余的收益。购买有冷冻期   
 int[] prepare = new int[n];  
             prepare[1] = Math.max(-prices[0], -prices[1]);  
             //done[i]:无限次购买的情况习，在0-i时间最后一次卖出所能得到的收益，由于是卖出，所以不考虑冷冻期  
             int[] done = new int[n];  
             done[1] = Math.max(prices[1] - prices[0], 0);  
             for (int i = 2; i < n; i++) {  
                 //在i时刻，done只有卖出或者不卖出  
                 done[i]=Math.max(done[i-1],prepare[i-1]+prices[i]);  
                 //在i时刻，prepare只有买入或者不买入的情况，但是要考虑冷冻期  
                 prepare[i]=Math.max(prepare[i-1],done[i-2]-prices[i]);  
             }  
             return done[n-1];  
         }  
         //空间压缩版本  
         public int maxProfit2(int[] prices) {  
             int n = prices.length;  
             if (n < 2) {  
                 return 0;  
             }  
             //prepare:无限次购买的情况下，在0-i时间内最后一次购买所剩余的收益。购买有冷冻期   
 int prepare = Math.max(-prices[0], -prices[1]);  
             //done[i]:无限次购买的情况习，在0-i时间最后一次卖出所能得到的收益，由于是卖出，所以不考虑冷冻期  
             int done1= Math.max(prices[1] - prices[0], 0);  
             int done2=0;  
             for (int i = 2,temp; i < n; i++) {  
                 //在i时刻，done只有卖出或者不卖出  
                 temp=done1;  
                 done1=Math.max(done1,prepare+prices[i]);  
                 //在i时刻，prepare只有买入或者不买入的情况，但是要考虑冷冻期  
                 prepare=Math.max(prepare,done2-prices[i]);  
                 done2=temp;  
             }  
             return done1;  
         }  
     }  
 }

7、DI序列的有效排列

题目描述：给定一个长度为 n 的字符串 s ，其中 s[i] 是:

“D” 意味着减少，或者
“I” 意味着增加

有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i：

如果 s[i] == 'D'，那么 perm[i] > perm[i+1]，以及；
如果 s[i] == 'I'，那么 perm[i] < perm[i+1]。

返回 有效排列 perm的数量 。因为答案可能很大，所以请返回你的答案对 109 + 7 取余。

示例 1：

输入：s = "DID" 输出：5 解释： (0, 1, 2, 3) 的五个有效排列是： (1, 0, 3, 2) (2, 0, 3, 1) (2, 1, 3, 0) (3, 0, 2, 1) (3, 1, 2, 0)

示例 2:

输入: s = "D" 输出: 1

提示:

n == s.length
1 <= n <= 200
s[i] 不是 'I' 就是 'D'

解题思路：

不需要知道第i位置的字符是哪一个，只需要知道比i-1字符小的还有多少个
状态设计优化的内容
后续优化枚举的时候注意i+less+more=n, 当上升趋势的时候，范围为less---less+more-1, 即less+n-less-i-1, 即n-i-1

项目名称	内容填写（每道题一行填写）
📘 题目编号 / 标题	LeetCode 903 + DI序列的有效排列
🧠 题目关键词（原文关键词）	`n` 的字符串 `s` ，其中 `s[i]` 是: - `“D”` 意味着减少，或者 - `“I”` 意味着增加，有效排列， *有效排列* `perm`的数量
🧩 抽象问题类型（题目本质）	排列数模型
🔍 数据规模 / 限制	- `n == s.length` - `1 <= n <= 200` - `s[i]` 不是 `'I'` 就是 `'D'`
🧭 我的初步思路	动态规划
✅ 正确解法类型	动态规划
❗ 没想到的原因	想不出来记忆化搜索
📦 归入的题型分类	动态规划类
🧠 触发词（以后遇到就联想）	DI排序数->动态规划
🧪 解法一句话总结	每次只记录改给那个位置放数值了，不关系前面放了那些数值，只关心还能用的数值中比上一个放的数值小的还有多少个

代码如下

 package main.java.class082;  
   
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code07_DiSequence  
  * @description: DI序列的有效排列  
  * // 给定一个长度为n的字符串s，其中s[i]是:  
  * // "D"意味着减少，"I"意味着增加  
  * // 有效排列是对有n+1个在[0,n]范围内的整数的一个排列perm，使得对所有的i：  
  * // 如果 s[i] == 'D'，那么 perm[i] > perm[i+1]  
  * // 如果 s[i] == 'I'，那么 perm[i] < perm[i+1]  
  * // 返回有效排列的perm的数量  
  * // 因为答案可能很大，答案对 1000000007 取模  
  * // 测试链接 : https://leetcode.cn/problems/valid-permutations-for-di-sequence/  
  * @author: zs宝  
  * @create: 2025-10-03 10:50  
  * @Version 1.0  
  **/public class Code07_DiSequence {  
     class Solution {  
         public int numPermsDISequence(String s) {  
             return numPermsDISequence3(s);  
         }  
   
         //记忆化搜索  
         public int numPermsDISequence1(String s) {  
             //这里有一种假设，0位置左边的时一个无穷大，要求满足D趋势  
             int[][] dp = new int[s.length() + 2][s.length() + 2];  
             return f1(s.toCharArray(), 0, s.length() + 1, s.length() + 1, dp);  
         }  
   
         /**  
          当前来到i位置，i-1位置的数字已经确定，i位置的数字还没确定,总共有n个数值  
          i-1位置和i位置的关系，是s[i-1] : D、I  
          0~i-1范围上是已经使用过的数字，i个  
          还没有使用过的数字中，比i-1位置的数字小的，有less个  
          还没有使用过的数字中，比i-1位置的数字大的，有n - i - less个  
          返回后续还有多少种有效的排列         比i-1小的数值还剩下less个  
          */  
         public int f1(char[] s, int i, int less, int n, int[][] dp) {  
             int ans = 0;  
             if (dp[i][less] != 0) {  
                 return dp[i][less];  
             }  
             if (i == n) {  
                 ans = 1;  
             } else if (i == 0 || s[i - 1] == 'D') {  
                 //由于0位置左边时无穷大，所以只能是下降趋势  
                 //或者当前为下降趋势  
                 for (int nextLess = 0; nextLess < less; nextLess++) {  
                     ans += f1(s, i + 1, nextLess, n, dp);  
                 }  
             } else {  
                 //s当前位置表示要一个上升趋势  
                 for (int nextLess = less, k = 0; k < n - i - less; k++, nextLess++) {  
                     ans += f1(s, i + 1, nextLess, n, dp);  
                 }  
             }  
             dp[i][less] = ans;  
             return ans;  
         }  
   
         //严格按照位置依赖的动态规划  
         public int numPermsDISequence2(String str) {  
             int MOD=1000000007;  
             char[] s = str.toCharArray();  
             int n = s.length + 1;  
             int[][] dp = new int[n + 1][n + 1];  
             for (int less = 0; less <= n; less++) {  
                 dp[n][less] = 1;  
             }  
   
             for (int i = n - 1; i >= 0; i--) {  
                 for(int less=0;less<=n;less++){  
                     if(i == 0 || s[i - 1] == 'D'){  
                         for(int nextLess=0;nextLess<less;nextLess++){  
                             dp[i][less]=(dp[i][less]+dp[i+1][nextLess])%MOD;  
                         }  
                     }else{  
                         for(int nextLess=less,k=0;k<n-i-less;k++,nextLess++){  
                             dp[i][less]=(dp[i][less]+dp[i+1][nextLess])%MOD;  
                         }  
                     }  
                 }  
             }  
             return dp[0][n];  
         }  
   
   
         //严格按照位置依赖的动态规划+观察法优化枚举  
         public int numPermsDISequence3(String str) {  
             int MOD=1000000007;  
             char[] s = str.toCharArray();  
             int n = s.length + 1;  
             int[][] dp = new int[n + 1][n + 1];  
             for (int less = 0; less <= n; less++) {  
                 dp[n][less] = 1;  
             }  
   
             for (int i = n - 1; i >= 0; i--) {  
                 if(i==0 || s[i-1]=='D'){  
                     dp[i][1]=dp[i+1][0];  
                     for(int less=2;less<=n;less++){  
                         dp[i][less]=(dp[i][less-1]+dp[i+1][less-1])%MOD;  
                     }  
                 }else{  
                     dp[i][n-i-1]=dp[i+1][n-i-1];  
                     for(int less=n-i-2;less>=0;less-- ){  
                         dp[i][less]=(dp[i][less+1]+dp[i+1][less])%MOD;  
                     }  
                 }  
             }  
             return dp[0][n];  
         }  
   
     }  
 }

参考资料

左程云-算法通关系列-082

如果觉得文章对你有用，请随意赞赏

算法动态规划

动态规划17：用观察优化枚举-上

https://zshunbao.top/archives/dong-tai-gui-hua-17-yong-guan-cha-you-hua-mei-ju-shang

作者

zs宝

发布于

2025-10-03

更新于

2025-10-03

许可协议

CC BY 4.0