浅谈股票类问题

题面传送门 这道题显然是对于每个卖出股票，在前面找到最小的买进，统计答案即可。 代码实现:

class Solution { public: int maxProfit(vector<int>& prices) { int a[1000039]; int i,j,ans=0,tot=0; int n=prices.size()-1; for(i=0;i<=n;i++) a[i]=prices[i]; for(i=n;i>=0;i--){ ans=max(ans,a[i]); tot=max(tot,ans-a[i]); } return tot; } };

题面传送门 对于每两天价格作差。 可以发现在第一天买进，第三天卖出等同于第一天买进，第二天卖出再买进，第三天卖出。 那么对于每两天之差，如果能赚那么就买进即可。 代码实现:

class Solution { public: int b[30039],ans=0; int maxProfit(vector<int>& prices) { int a[30039],i; int n=prices.size()-1; for(i=0;i<=n;i++){ a[i]=prices[i]; } for(i=0;i<n;i++) b[i]=a[i+1]-a[i]; for(i=0;i<n;i++)ans+=max(b[i],0); return ans; } };

题面传送门 题面传送门 这两道题是同一道题。 考虑$dp$ 设$d{p}_{i,j}$表示买了第$i$次在$j$支股票能有的利润。 那么转移方程就是$d{p}_{i,j}=\underset{k=1}{\overset{j-1}{\max }}d{p}_{i-1,k}+a_j-a_k$ 但这样是$O(n^{2}k)$的，不足以通过。 考虑分开计算，$d{p}_{i,j}=(\underset{k=1}{\overset{j-1}{\max }}d{p}_{i-1,k}-a_k)+a_j$ 前面一部分可以迭代计算。 那么就是$O(nk)$的了。 然后可以发现一个性质:至多只能交易$\frac{n}{2}$次。 所以就可以过去了。 代码实现:

class Solution { public: int n,m,k,x,y,z,ans,tot,a[100039],dp[2][100038],now,last; int maxProfit(int k, vector<int>& prices) { int i,j;n=prices.size()-1; if(n==-1) return 0; for(i=0;i<=n;i++){ a[i]=prices[i]; } if(k>(n+1)/2)k=(n+1)/2; for(i=1;i<=k;i++){ now=i&1;last=now^1;ans=-1e9; for(j=0;j<=n;j++){ dp[now][j]=0; if(j) dp[now][j]=dp[now][j-1]; dp[now][j]=max(dp[now][j],ans+a[j]); ans=max(ans,dp[last][j]-a[j]); tot=max(tot,dp[now][j]); // printf("%d ",dp[now][j]); } // printf("\n"); } return tot; } };

题面传送门 只要将第三题的方程式改一下就好了。改成从前一天转移。 代码实现:

class Solution { public: int n,a[1000039],ans,tot,pus,dp[1000039]; int maxProfit(vector<int>& prices) { int i; n=prices.size()-1; for(i=0;i<=n;i++) a[i]=prices[i]; ans=-a[0]; for(i=1;i<=n;i++){ dp[i]=max(a[i]+ans,dp[i-1]); if(i>=2)ans=max(ans,dp[i-2]-a[i]); else if(i==1) ans=max(ans,-a[1]); tot=max(tot,dp[i]); printf("%d ",dp[i]); } return tot; } };

题面传送门 在前面的转移方程式上减去手续费即可。 代码实现:

class Solution { public: int n,m,k,x,y,z,a[100039],dp[100039],ans,tot,pus,i; int maxProfit(vector<int>& prices, int fee) { n=prices.size()-1;k=fee; for(i=0;i<=n;i++) a[i]=prices[i]; ans=-a[0]; for(i=1;i<=n;i++){ if(i) dp[i]=dp[i-1]; dp[i]=max(dp[i],ans+a[i]-k); ans=max(ans,dp[i]-a[i]); tot=max(tot,dp[i]); printf("%d ",dp[i]); } return tot; } };

股票交易 纪念品 具体可以参见我的题解 感觉这一类问题就是将原问题用状态表示，基本就是$d{p}_{i,j}$表示$i$次交易到了$j$张股票。然后状态转移就是从之前的转移。这个转移基本可以迭代优化。