假设我们有一个数组,第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的3D数组
定义一种称为pre()的方法
用于初始化i:= 0,当i <= N时,将i增加1做-
dp [i,j,1]:=-1,dp [i,j,0]:=-1
对于初始化j:= 0,当j <= N时,将j增加1做-
定义一个称为Solve()的方法,它将采用arr,i,n,k和status
如果我与n相同,那么,
回报-100000
如果状态不为零,则
返回0
如果dp [i,k,status]不等于-1,则,
返回dp [i,k,状态]
ans:= solve(arr,i + 1,n,k,status)
如果状态不为零,则
ans:= ans的最大值,solve(arr,i + 1,n,k-1,状态的倒数)+ arr [i]
否则-
ans:= ans,solve(arr,i + 1,n,k,状态逆的状态)的最大值-arr [i]
如果k> 0,
返回dp [i,k,status]:= ans
从主要方法中执行以下操作-
调用函数pre()
如果k> =价格的大小/ 2,那么,
如果价格[i]>价格[i-1],则ans = ans +价格[i]-价格[i-1]
回答:= 0
用于初始化i:= 1,当i <价格大小时,将i加1做-
返回ans
返回求解(prices,0,价格大小,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