Java之动态规划之股票问题

逃离我推掉我的手 2024-03-27 14:30 63阅读 0赞

**目录**

0.动态规划问题

一.买卖股票的最佳时机

1.题目描述

2.问题分析

3.代码实现

二.买卖股票的最佳时机 II

1.题目描述

2.问题分析

3.代码实现

三.买卖股票的最佳时机 III

1.题目描述

2.问题分析

3.代码实现

四.买卖股票的最佳时机 IV

1.题目描述

2.问题分析

3.代码实现

五.最佳买卖股票时机含冷冻期

1.题目描述

2.问题分析

3.代码实现

六.买卖股票的最佳时机含手续费

1.题目描述

2.问题分析

3.代码实现

--------------------

## 0.动态规划问题 ##

**动态规划**(**D**ynamic **P**rogramming)算法的核心思想是:将大问题划分为小问题,进行解决，从而一步步获取最优解的处理算法

动态规划对于解决最优子结构啊和重叠子问题等问题时候,有着很好的应用

对于**动态规划问题**,大致可以分为以下几步:

1.  确定dp数组（dp table）以及下标的含义
2.  确定递推公式
3.  dp数组如何初始化
4.  确定遍历顺序
5.  举例推导dp数组

## 一.买卖股票的最佳时机 ##

### 1.题目描述 ###

> 给定一个数组 `prices` ，它的第 `i` 个元素 `prices[i]` 表示一支给定股票第 `i` 天的价格。
> 
> 你只能选择 **某一天** 买入这只股票，并选择在 **未来的某一个不同的日子** 卖出该股票。设计一个算法来计算你所能获取的最大利润。
> 
> 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 `0` 。

力扣: [力扣][Link 1]

### 2.问题分析 ###

这一题买卖股票并且只能买卖一次,所有对于你对于股票应该有**两种状态**,一种是持有股票的状态,一种是不持有股票时候的状态

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

**1.确定dp数组（dp table）以及下标的含义**

**dp\[i\]\[0\]表示第i天持有股票所得的最多现金,dp\[i\]\[1\]表示第i天不持有股票所得的最多现金**

**2.确定递推公式**

**因为只能买入一次,并且卖出一次,**

**先来分析第i天持有股票的情况,如果第i天持有股票,那么只有两种情况,一种第i天之前已经买入股票了,一种第i天的时候刚好买入股票,应该取这两者的最大值作为dp\[i\]\[0\]**

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

**再来分析第i天不持有股票的情况,如果第i天不持有股票,那么也只有两种情况,一种第i天之前已经卖出股票了,一种第i天刚好卖出股票,应该取这两者的最大值作为dp\[i\]\[1\]**

**dp\[i\]\[1\]=max(dp\[i-1\]\[1\],dp\[i-1\]\[0\]+prices\[i\])**

dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);

**3.dp数组如何初始化**

**由递推公式可以看出dp\[i\]\[0\]或dp\[i\]\[1\]均有前面一项推出来,所以应该至少初始化dp\[0\]\[0\]和dp\[0\]\[1\],由题意可知,第0天持有股票便是在第0天买入股票,所以dp\[0\]\[0\]=prices\[0\],第0天不持有股票就是不买入股票,dp\[0\]\[1\]=0**

**4.确定遍历顺序**

**由递推公式可以看出dp\[i\]\[0\]或dp\[i\]\[1\]均有前面一项推出来,所以应该是从左到右进行遍历**

**5.举例推导dp数组**

**对于prices=\{7,1,5,3,6,4\}进行填表**

### 3.代码实现 ###

public int maxProfit(int[] prices) {
            //dp[i][0] 表示第i天持有股票所得最多现金
            //dp[i][1] 表示第i天不持有股票所得最多现金
            int[][] dp = new int[prices.length][2];
            //初始化
            dp[0][0] = -prices[0];
            dp[0][1] = 0;
            for (int i = 1; i < prices.length; ++i) {
                dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);//不购入股票(保持和之前一样)和购入股票的最大值
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//不卖出股票(保持一样)和卖出股票
            }
            return dp[prices.length - 1][1];
    
        }

## 二.买卖股票的最佳时机 II ##

### 1.题目描述 ###

> 给你一个整数数组 `prices` ，其中 `prices[i]` 表示某支股票第 `i` 天的价格。
> 
> 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 **最多** 只能持有 **一股** 股票。你也可以先购买，然后在 **同一天** 出售。
> 
> 返回 *你能获得的 **最大** 利润* 。

力扣:[力扣][Link 2]

### 2.问题分析 ###

这一题与上一题唯一的不同就是可以购买多次股票,然后再卖出,其他分析与上一题都一样,这一题主要就是在递推公式上有不同

**1.确定递推公式**

**dp\[i\]\[0\]仍然表示在第i天持有股票所有的最大现金.**

**在第i天可以选择买入股票,也可以选择不买入,选择不买入(之前已经买入了)就是dp\[i-1\]\[0\],和之前一样,选择当天买入的话就和前一题不一样了,前一题因为只可能买入一次,所以持有股票的时候,(当天买入的情况)一定是0-prices\[i\],这一题因为之前可能已经买入并且卖出的情况,所以dp\[i\]\[0\]与dp\[i-1\]\[1\]联系起来 递推公式为:dp\[i\]\[0\]=max(dp\[i-1\]\[0\],dp\[i-1\]\[1\]-prices\[i\])**

**dp\[i\]\[1\]仍然表示在第i天不持有股票所有的最大现金.** **和之前的分析一样**

**递推公式为dp\[i\]\[1\]=max(dp\[i-1\]\[1\],dp\[i-1\]\[0\]+prices\[i\])**

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);

**2.举例推导dp数组**

**对于prices = \[7,1,5,3,6,4\]进行推导**

### 3.代码实现 ###

public int maxProfit2(int[] prices) {
            int[][] dp = new int[prices.length][2];
            dp[0][0] -= prices[0];
            dp[0][1] = 0;
            for (int i = 1; i < prices.length; ++i) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);//不购入股票(保持和之前一样)和购入股票的最大值
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//不卖出股票(保持一样)和卖出股票
            }
         
            return dp[prices.length - 1][1];
        }

## 三.买卖股票的最佳时机 III ##

### 1.题目描述 ###

> 给定一个数组，它的第`i` 个元素是一支给定的股票在第 `i`天的价格。
> 
> 设计一个算法来计算你所能获取的最大利润。你最多可以完成 **两笔** 交易。
> 
> **注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

力扣:[力扣][Link 3]

### 2.问题分析 ###

这个题目是最多可以完成**两笔**交易,说明你可以不交易,也可以选择完成一笔交易,也可以完成两笔交易,不能像第二个问题一样完成多笔交易

这个时候主要就是dp数组与前几题不一样,思路几乎一样

**1.确定dp数组（dp table）以及下标的含义**

**dp\[i\]\[j\], 一天一共有5种状态(并不是一定是第i天才到达这种状态)**

1.  **不进行操作**
2.  **第一次持有股票**
3.  **第一次不持有股票**
4.  **第二次持有股票**
5.  **第二次不持有股票**

**dp\[i\]\[j\]的含义是,在第i天,处于j中状态下的拥有的最多现金**

**2.确定递推公式**

**0.dp\[i\]\[0\]恒等于0**

**①达到dp\[i\]\[1\]这个状态有两种情况,第一种,之前已经处于这种状态,并且今天不进行任何操作,第二种,当天买入股票从而处于这种情况,所以dp\[i\]\[1\]=max(dp\[i-1\]\[1\],dp\[i-1\]\[0\]-prices\[i\])**

**②达到dp\[i\]\[2\]这个状态同样有两种情况,第一种,之前已经处于这种状态,并且今天不进行任何操作,第二种,当天卖出股票从而处于这种情况,所以dp\[i\]\[0\]=max(dp\[i-1\]\[2\],dp\[i-1\]\[1\]+prices\[i\])**

**③达到dp\[i\]\[3\]这个状态同样有两种情况,第一种,之前已经处于这种状态,并且今天不进行任何操作,第二种,当天买入股票从而处于这种情况,所以dp\[i\]\[0\]=max(dp\[i-1\]\[3\],dp\[i-1\]\[2\]-prices\[i\])**

**④达到dp\[i\]\[4\]这个状态同样有两种情况,第一种,之前已经处于这种状态,并且今天不进行任何操作,第二种,当天卖出股票从而处于这种情况,所以dp\[i\]\[0\]=max(dp\[i-1\]\[4\],dp\[i-1\]\[3\]+prices\[i\])**

dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
                dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
                dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

**3.dp数组如何初始化**

**根据递推公式,对所有的状态都需要对第一个进行初始化,dp\[0\]\[0\]=0,dp\[0\]\[1\]=0-prices\[0\]没什么问题,主要就是dp\[0\]\[2\]=0,dp\[0\]\[3\]=0-prices\[0\],dp\[0\]\[4\]=0-prices\[0\],因为可以选择在当天卖出,当天再买入,再卖出,所以这些初始化是这些**

dp[0][1] = -prices[0];
            dp[0][3] = -prices[0];

**4.确定遍历顺序**

**和之前一样**

**5.举例推导dp数组**

### 3.代码实现 ###

public int maxProfit3(int[] prices) {
            //表示的是第i天，买入股票的状态，
            int[][] dp = new int[prices.length][5];
            dp[0][1] = -prices[0];
            dp[0][3] = -prices[0];
            for (int i = 1; i < prices.length; ++i) {
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);//不购入股票(保持和之前一样)和购入股票的最大值
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);//不卖出股票(保持一样)和卖出股票
                dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);//不购入股票(保持和之前一样)和购入股票的最大值
                dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);//不卖出股票(保持一样)和卖出股票
    
            }
            
            return dp[prices.length - 1][4];
    
        }

## 四.买卖股票的最佳时机 IV ##

### 1.题目描述 ###

> 给定一个整数数组 `prices` ，它的第`i` 个元素 `prices[i]` 是一支给定的股票在第 `i`天的价格。
> 
> 设计一个算法来计算你所能获取的最大利润。你最多可以完成 **k** 笔交易。
> 
> **注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

力扣:[力扣][Link 4]

### 2.问题分析 ###

**这一题是**买卖股票的最佳时机 III**的进阶版,主要就是将最多买2次转换为最多k次,将第一题的直接复制,转换为一个关于j的for循环,赋值还和上一题一样,只不过这一次也要加上for循环,直接看代码更好理解一点**

### 3.代码实现 ###

int[][] dp = new int[prices.length][2 * k + 1];
            for (int i = 1; i < 2 * k + 1; i += 2) {
                dp[0][i] = -prices[0];
            }
            for (int i = 1; i < prices.length; ++i) {
                for (int j = 1; j < 2 * k + 1; ++j) {
                    if (j % 2 != 0)
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                    else
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
    
                }
            }
    
            return dp[prices.length - 1][2 * k];

## 五.最佳买卖股票时机含冷冻期 ##

### 1.题目描述 ###

> 给定一个整数数组`prices`，其中第 `prices[i]` 表示第 `i` 天的股票价格 。
> 
> 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
> 
>  *  卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
> 
> **注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

力扣:[力扣][Link 5]

### 2.问题分析 ###

这个题目相当于**买卖股票的最佳时机 II**题目的进阶版,主要就是多了一个冷冻期,也就是多了一个冷冻期状态

在**II**中我们解决的问题解决的问题就两个状态,一个是持有股票的状态,一个是未持有股票的状态,分析这一题,我们多了个冷冻期,如何进入冷冻期呢?那么它的前一天一定是卖出股票的状态,这样才能达到冷冻期,冷冻期在进入可自由买入股票状态,这样就有以下**四个状态**

1.  **持有股票状态(不一定当天买入股票,可能之前就已经买入了,保持之前的状态)**
2.  **可自由买入股票状态(冷冻期之后的状态)**
3.  **当天卖出股票状态(在今天卖出股票)**
4.  **冷冻期状态(前一天是卖出股票状态)**

**1.确定dp数组（dp table）以及下标的含义**

**dp\[i\]\[j\],在第i天状态是j所持有的最大现金**

**2.确定递推公式**

**状态一:**

**①前一天可能处于状态四,然后买入股票进入持有股票状态 dp\[i\]\[0\]=dp\[i-1\]\[3\]**

**②前一天可能是状态二,然后买入股票进入持有股票状态 dp\[i\]\[0\]=dp\[i-1\]\[1\]**

**③前一天可能是状态一,保持之前状态 dp\[i\]\[0\]=dp\[i-1\]\[0\]**

**状态二:**

**①前一天是状态四,解除冷冻期进入状态二 dp\[i\]\[1\]=dp\[i-1\]\[3\]**

**②前一天是状态二,保持之前状态 dp\[i\]\[1\]=dp\[i-1\]\[1\]**

**状态三:**

**①前一天是状态一,今天卖出股票 dp\[i\]\[2\]=dp\[i-1\]\[0\]**

**状态四:**

**①前一天是状态三,今天进入冷冻期 dp\[i\]\[3\]=dp\[i-1\]\[2\]**

//持有股票的状态
                dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
                //未持有股票且不在冷冻期状态
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
                //当天卖出股票的状态
                dp[i][2] = dp[i - 1][0] + prices[i];
                //冷冻期状态
                dp[i][3] = dp[i - 1][2];

**3.dp数组如何初始化**

**需要对第0天进行初始化,持有股票状态就是在今天进行买入dp\[0\]\[0\]=-price\[0\]**

**其他状态今天买入卖出变为0,所以全部赋为0**

**4.确定遍历顺序**

**和之前一样**

**5.举例推导dp数组**

### 3.代码实现 ###

int[][] dp = new int[prices.length][4];
            dp[0][0] = -prices[0];
    
            for (int i = 1; i < prices.length; ++i) {
                //持有股票的状态
                dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
                //未持有股票且不在冷冻期状态
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
                //当天卖出股票的状态
                dp[i][2] = dp[i - 1][0] + prices[i];
                //冷冻期状态
                dp[i][3] = dp[i - 1][2];
            }
            return Math.max(dp[prices.length - 1][2], Math.max(dp[prices.length - 1][3], dp[prices.length - 1][1]));

## 六.买卖股票的最佳时机含手续费 ##

### 1.题目描述 ###

> 给定一个整数数组 `prices`，其中 `prices[i]`表示第 `i` 天的股票价格 ；整数 `fee` 代表了交易股票的手续费用。
> 
> 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
> 
> 返回获得利润的最大值。
> 
> **注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

力扣:[力扣][Link 6]

### 2.问题分析 ###

这一题几乎和**买卖股票的最佳时机 II一样,唯一的不同就是在最后完成交易的时候再减去手续费就可以了**

**1.确定递推公式**

**dp\[i\]\[0\] = max(dp\[i - 1\]\[0\], dp\[i - 1\]\[1\] - prices\[i\]);**

**dp\[i\]\[1\] = max(dp\[i - 1\]\[1\], dp\[i - 1\]\[0\] + prices\[i\] - fee);**

**5.举例推导dp数组**

**不进行推导**

### 3.代码实现 ###

public int maxProfit(int[] prices, int fee) {
            int[][] dp = new int[prices.length][2];
            dp[0][0] = -prices[0];
            for (int i = 1; i < dp.length; ++i) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
            }
            return dp[prices.length - 1][1];
        }

[Link 1]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
[Link 2]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
[Link 3]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
[Link 4]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
[Link 5]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[Link 6]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/