数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++实现股票买卖最佳时机 IV
假设我们有一个数组，其中第 i 个元素代表第 i 天的股票价格。我们必须设计一个算法来找到最大利润。我们最多可以完成 k 笔交易。例如，如果输入为 [3,2,6,4,0,3] 且 k = 2，则输出为 7，因为在第 2 天（价格 = 2）买入，在第 3 天（价格 = 6）卖出，利润为 6-2 = 4。然后在第 5 天（价格为 0）买入，在第 6 天（价格为 3）卖出，利润为 3-0 = 3。
为了解决这个问题，我们将遵循以下步骤：
定义一个大小为 N+5 x N+5 x 2 的三维数组。
定义一个名为 pre() 的方法。
初始化 i := 0，当 i<=N 时，i 自增 1：
初始化 j := 0，当 j<=N 时，j 自增 1：
dp[i, j, 1] := -1, dp[i, j, 0] := -1
定义一个名为 solve() 的方法，它将接收 arr, i, n, k 和 status 作为参数。
如果 i 等于 n，则：
如果 status 不为零，则：
返回 -100000
返回 0
如果 dp[i, k, status] 不等于 -1，则：
返回 dp[i, k, status]
ans := solve(arr, i + 1, n, k, status)
如果 status 不为零，则：
ans := max(ans, solve(arr, i + 1, n, k - 1, !status) + arr[i])
否则：
如果 k>0，则：
ans := max(ans, solve(arr, i + 1, n, k, !status) - arr[i])
返回 dp[i, k, status] := ans
在主方法中执行以下操作：
调用函数 pre()
如果 k >= prices.size() / 2，则：
ans := 0
初始化 i := 1，当 i < prices.size() 时，i 自增 1：
如果 prices[i] > prices[i-1]，则 ans = ans + prices[i] - prices[i - 1]
返回 ans
返回 solve(prices, 0, prices.size(), k, 0)
示例
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
typedef int lli;
const lli N = 1000;
lli dp[N + 5][N + 5][2];
class Solution {
public:
void pre(){
for(lli i =0;i<=N;i++){
for(lli j = 0;j<=N;j++){
dp[i][j][1]=-1;
dp[i][j][0]=-1;
}
}
}
lli solve(vector<int> &arr, lli i,lli n,lli k, lli status){
if(i == n){
if(status)return -100000;
return 0;
}
if(dp[i][k][status]!=-1)return dp[i][k][status];
lli ans = solve(arr, i+1,n,k,status);
if(status){
ans = max(ans,solve(arr,i+1,n,k-1,!status)+ arr[i]) ;
} else {
if(k>0){
ans = max(ans,(lli)solve(arr,i+1,n,k,!status)- arr[i]) ;
}
}
return dp[i][k][status] = ans;
}
int maxProfit(int k, vector<int>& prices) {
pre();
if(k>=prices.size()/2){
int ans = 0;
for(int i = 1; i < prices.size(); i++){
if(prices[i] > prices[i-1])ans += prices[i] - prices[i-1];
}
return ans;
}
return solve(prices,0,prices.size(),k,0);
}
};
main(){
Solution ob;
vector<int> v = {3,2,6,4,0,3};
cout << (ob.maxProfit(2, v));
}输入
{ 3,2,6,4,0,3}输出
7
136 次浏览
