买卖股票
- 本文所讲解的内容与LeetCode122. 买卖股票的最佳时机ll,这道题题意相同,阅读完本文后可以自行挑战一下
- 力扣链接
题目叙述:
给定一个长度为N的数组,数组中的第i个数字表示一个给定股票在第i天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉悠前的股票)。一次买入卖出合为一笔交易。
输入格式:
第一行包含整数 N,表示天数。第二行包含N个不大于10000的正整数表示每天股票的价格。
输出格式
输出一个整数,表示最大利润。
输入样例1
6
7 1 5 3 4 6
输出样例1
7
输入样例2
5
7 6 4 3 1
输出样例2
0
样例解释:
- 样例1:在第2天买入,在第3天卖出,这笔交易所能获得利润=5-1=4。随后在第4天买入,在第6天卖出,这笔交易所能获得利润=6-3=3。共得利润4+3 =7
- 样例2:在这种情况下,不进行任何交易,所以最大利润为 0。
动态规划思路讲解:
- 我们分析总利润可知,总利润是关于天数
i
的函数,并且在第i天的时候,只有两种状态与之对应- 1.手中无票:
dp[i][0]
- 2.手中有票:
dp[i][1]
- 1.手中无票:
- 所以说我们可以设置
dp[i][0],dp[i][1]
为状态变量,然后进行状态的转移,最终得出我们需要的答案。
1.状态变量的含义
dp[i][0]
表示第i
天,手中无票时能够获取的最大利润dp[i][1]
表示第i
天,手中有票时能够获取的最大利润
2. 递推公式
-
我们可以使用带权的有向图来生动的理解这个过程,我们要知道递推公式,就要了解状态转移的那个过程,也就是我们当前的状态是由以前的哪些状态推导而来。
-
dp[i][0]
表示第i天,手中无票时能获取的最大利润,我们可以通过dp[i-1][0]
和dp[i-1][1]
,也就是第i-1
天,手中有票或者手中无票这两个状态推导而来,如果是第i-1
天手中无票,那么表示没有发生交易,那么dp[i][0]=dp[i-1][0]
,反之,从i-1
天有票到第i
天无票,那么意味着我们在第i天卖掉了股票,此时dp[i][0]=dp[i-1][1]+w[i]
,由于我们是取最大利润,所以说是取二者的最大值,即:
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+w[i]);
-
dp[i][1]
也是同理,跟上面的推导方式差不多,所以我就不在赘述了
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-w[i]);
-
-
所以说,总的递推公式如下:
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+w[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-w[i]);
3.如何初始化?
- 我们由这个递推公式,如何初始化边界条件呢?
- 假设我们从第1天开始,到第n天结束,那么我们第一天的两个状态就是边界条件
dp[1][0]=0; //第1天无票的最大利润就是0
dp[1][1]=-w[1]; //第1天就有票证明我买了第一天的那个股票
4. 遍历顺序
- 由递推公式可知,我们的状态变量
dp[i][0],dp[i][1]
取决于dp[i-1][0],dp[i-1][1]
。所以说我们的遍历顺序是从前到后进行遍历。
5. 举例打印dp数组
- 在本题,读者可以自行在for循环内进行插入printf语句进行验证我们dp数组的正确性
代码:
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int w[N],dp[N][2];
int n;
int main(){
scanf("%d", &n);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
dp[1][0]=0; dp[1][1]=-w[1];
for(int i=2; i<=n; ++i){
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+w[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-w[i]);
}
//第n天的时候,手中无票一定是利润最大,所以说不用取二者最大值了。
cout<<dp[n][0];
}
LeetCode122的参考代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int> > dp(prices.size(),vector<int>(2));
//进行初始化条件
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[prices.size() - 1][0];
}
};
标签:int,ll,样例,LeetCode122,prices,无票,dp,利润
From: https://www.cnblogs.com/Tomorrowland/p/18407226