本文最后更新于 426 天前，其中的信息可能已经有所发展或是发生改变。
题目描述
- 给你一个整数数组
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 = [1,2,3,4,5]
输出： 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
解题思路
本题与Leetcode123不同之处在于至多可以交易k次。
- 确定dp数组以及下标的含义
dp[i][j]：第i天的状态为j，所剩下的最大现金。 j的状态：
- 0 表示不操作
- 1 表示第1次买入
- 2 表示第2次买出
- 3 表示第3次买入
- 4 表示第4次买出
- …..
除了0以外，奇数买入，偶数卖出
确定递推公式
dp[i][1]:
第i天没有操作：dp[i][1]=dp[i-1][1]
第i天买入股票：dp[i][1]=dp[i-1][0]-prices[i]
取两者最大值：
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])dp[i][2]:第i天没有操作：dp[i][2]=dp[i-1][2]
第i天买入股票：dp[i][2]=dp[i-1][1]-prices[i]
取两者最大值：
dp[i][2]=max(dp[i-1][2],dp[i-1][1]-prices[i])…
- dp数组初始化
dp[i][0] = 0dp[i][1] = -prices[0]dp[i][2] = 0dp[i][3] = -prices[0]
…
代码实现
- 核心模式
class Solution{
public:
int maxProfit(int k, vector<int>& prices){
int len = prices.size();
if (len == 0) return 0;
vector<vector<int>> dp(len, vector<int>(2 * k + 1, 0));
// initialize the DP array
for (int j = 1; j < 2 * k; j += 2){
dp[0][j] = -prices[0];
}
// traversal
for (int i = 1; i < len; i++){
// recursive formula
for (int j = 0; j < 2 * k - 1; j += 2){
dp[i][j + 1] = std::max(dp[i -1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = std::max(dp[i -1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[len - 1][2 * k];
}
};
- ACM 模式
"dynamicPro.h"
#include <iostream>
#include "dynamicPro.h"
class Solution{
public:
int maxProfit(int k, vector<int>& prices){
int len = prices.size();
if (len == 0) return 0;
vector<vector<int>> dp(len, vector<int>(2 * k + 1, 0));
// initialize the DP array
for (int j = 1; j < 2 * k; j += 2){
dp[0][j] = -prices[0];
}
// traversal
for (int i = 1; i < len; i++){
// recursive formula
for (int j = 0; j < 2 * k - 1; j += 2){
dp[i][j + 1] = std::max(dp[i -1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = std::max(dp[i -1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
print2DVector(dp);
return dp[len - 1][2 * k];
}
};
int main(){
vector<int> case1 = {2, 4, 1};
vector<int> case2 = {3, 2, 6, 5, 0, 3};
Solution solution;
cout << "Result1's DP array = " << solution.maxProfit(2, case1) << endl;
cout << "Result2's DP array = " << solution.maxProfit(2, case2) << endl;
}
- 输出
Result1's DP array = [[0, -2, 0, -2, 0], [0, -2, 2, -2, 2], [0, -1, 2, 1, 2]]
2
Result2's DP array = [[0, -3, 0, -3, 0], [0, -2, 0, -2, 0], [0, -2, 4, -2, 4], [0, -2, 4, -1, 4], [0, 0, 4, 4, 4], [0, 0, 4, 4, 7]]
7