本文共 1840 字，大约阅读时间需要 6 分钟。

给定一个整数数组 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 <= 109

0 <= prices.length <= 1000

0 <= prices[i] <= 1000

初始化：

如果我们把买+卖算一次交易

那么这道题的限制是交易数，天数，手上有没有股票(有股票就不能买，没有股票就不能卖)

建立三维的数组：dp [k] [i] [2]

其中k表示的是交易次数，i表示的是第几天，2表示的是有两种状态：手上没有股票/手上有股票

dp [k] [i] [0] 数组中的数字表示的是到了第i天，交易了k次，手上没有股票获得的最大利益

dp [k] [i] [1] 数组中的数字表示的是到了第i天，交易了k次，手上持有股票获得的最大利益

在我们写转移方程之前我们还要先考虑之前提出来的问题–交易数怎么算，买+卖是一次交易，我的t表示的是交易次数，那我到底是买入的时候t要加一了，还是卖出的时候t才加一？

答：都可以，不同的定义就会有不同的实现

来看一下两者有什么不同

买入就算一次交易：

i天t次交易现在手上不持有 = max(i-1天t次交易手上不持有，i-1天t次交易手上持有 + i天卖出价格prices)

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

i天t次交易现在手上持有 = max(i-1天t次交易手上持有，i-1天t-1次交易手上不持有 - i天买入价格)

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

初始化

dp[t] [0] [0] 0天t次交易，手上不持有：可能的 0

dp[t] [0] [1] 0天t次交易，手上持有：不可能（0天没有股票，所以无法买入持有;持有说明至少进行了一次买入，买入就交易，因此这里不可能【不可能意思就是不能从这里转移】

dp[0] [i] [0] i天0次交易，手上不持有：0

dp[0] [i] [1] i天0次交易，手上持有：不可能（不交易手上不可能持有）

class Solution {
   	    public int maxProfit(int k, int[] prices) {
   	    	if(prices==null||prices.length==0||prices.length==1) {
   	    		return 0;	    	}	    	// 判断k次交易	    	if(k>(prices.length/2)) {
   	    		int sum = 0;	    		for(int i=1;i
   
    0?temp:0);	    		}	    		return sum;	    	}	    		    	// 动态数组	    	int[][][] dp = new int[k+1][prices.length+1][2];	    	// 初始化 交易 0天t次交易 手上持有 不可能	    	for(int t=0;t<=k;t++) {
   	    		dp[t][0][1] = Integer.MIN_VALUE;	    	}	    	// i天0次交易手上持有 不可能	    	for(int i=0;i
   

转载地址：https://codingchaozhang.blog.csdn.net/article/details/111309017 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！