2021-01-10 | 188. 买卖股票的最佳时机 IV

淩亂°似流年 2023-01-04 14:48 190阅读 0赞

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

给定一个整数数组 prices ，它的第 i 个元素 prices\[i\] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 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 。

提示：

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

### 2. 解题思路 ###

在题目121《买卖股票的最佳时机》中，我们只能进行一次买入卖出，在题目123《买卖股票的最佳时机 III》中，我们可以进行两次买入卖出操作。而在这道题目中，我们可以进行k次买入卖出操作。这里我们也可以使用**动态规划**来解答。

每次我们只能进行`[1, k]`次中的某次交易或不交易，所以可能有2k+1中状态：

*  无操作，一直没有买
 *  dp\[0\]：到最后只买了一笔，未卖出
 *  dp\[1\]：到最后只卖了一笔，并卖出
 *  dp\[2\]：到最后买了两笔，只卖出一笔
 *  dp\[3\]：到最后买了两笔，两笔都卖出
 *  dp\[4\]：到最后买了三笔，只卖出两笔
 *  ······

我们可以枚举一天的所有可能，取现金最大值：

*  不交易，现金 不变
 *  进行`[1, k]`的某次交易
    
     *  买入，现金 -= 当天股票价格
     *  卖出，现金 += 当天股票价格

**复杂度分析**

*  **时间复杂度**：O(n \* min(n, k))，其中 n 是数组 prices 的长度，即使用二重循环进行动态规划需要的时间。
 *  **空间复杂度**：O(min(n,k))。

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

/** * @param {number} k * @param {number[]} prices * @return {number} */
    var maxProfit = function(k, prices) { 
        const dp = new Int16Array(k * 2).fill(-prices[0])
        
        for (let i = 0; i < prices.length; i++) { 
            for (let j = 0; j < dp.length; j++) 
                { 
                    dp[j] = Math.max(dp[j], (dp[j - 1] || 0) + (j & 1 ? prices[i] : -prices[i]))
                }
        }
        return Math.max(0, ...dp) 
    };

### 4. 提交结果 ###

![在这里插入图片描述][2021011022050176.png]

[2021011022050176.png]: /images/20221119/4cf7c5335bbd483a8ecb93fd8c9dd8cb.png?