資料結構
網路
關係資料庫管理系統(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 次瀏覽
