股票问题(简单DP)
摘要
本文主要介绍了和DP相关的股票问题,分析比较简单,容易理解,适合刚接触DP的朋友们学习。
股票Ⅰ
题面
假设您有一个数组,第i个元素是第i天给定股票的价格。
如果只允许您最多完成一笔交易(即买入和卖出一股股票),请设计一种算法以找到最大的利润(卖出的价格-买入的价格)。
请注意,您不能在买股票之前卖出股票。
输入
多组输入数据
每组数据第一行一个数n,(1≤n≤105)
接下来一行n个数表示股票的价格(1≤ai≤109)
输出
每组数据一行一个数。
输入样例
1 | 5 |
输出样例
1 | 4 |
AC代码
1 |
|
分析
我们直接从DP的角度开始分析这个问题,首先看清题意,只能买入和卖出一股股票,并且卖出必须在买入之后完成。那么我们每一天的选择就是买或者不买或者卖,也就是有两种状态买buy和卖sell,而买入股票对应的就是花钱,我们最开始的钱为0,买入后就变会损失也就是-a[i],并且当天的总收益就为-a[i],也就是buy的值,卖出后则为收益也就是+a[i],并且当天的总收益就为buy+a[i]。所以我们就考虑当天买和之前买了(即与之前buy里的值进行比较)哪个收益更高,同时当天卖和之前已经卖了(即与之前sell里的值进行比较)哪个收益更高即可完成。
转移方程
- buy = max(buy, -a[i])
- sell = max(sell, buy+a[i])
HINT
首先观察数据范围发现最终结果是可能超int的,所以对buy和sell的定义应为long long,然后是buy的初始值应该设置为负值而不是0,因为第一次买入的时候此时总收益就为负值。
股票Ⅱ
题面
假设您有一个数组,第i个元素是第i天给定股票的价格。
设计算法以找到最大的利润。您可以根据需要完成尽可能多的交易。
请注意,无法同时进行多项交易(即必须先出售股票才能再次购买)
输入
多组输入数据
每组数据第一行一个数n,(1≤n≤105)
接下来一行n个数表示股票的价格(1≤ai≤109)
输出
每组数据一行一个数
输入样例
1 | 5 |
输出样例
1 | 4 |
AC代码
1 |
|
分析
我们直接从上一问的思路继续分析,本题是要求利润最大并且可以完成任意多的交易(即可以买了又卖卖了再买),那我们还是同样分析,买了之后当天的总收益为sell-a[i](因为之前是处于卖了之后的状态所以用sell来减),然后卖了之后当天的总收益为buy-a[i](因为之前是处于买了之后的状态所以用buy来减),然后我们考虑每一天的情况即可。
转移方程
buy = max(buy, sell-a[i])
sell = max(sell, buy+a[i])
HINT
还是一样需要注意数据类型的选择和buy的初始赋值,然后是sell最初值置0才能保证第一次买后总收益的正确性。
股票Ⅲ
题面
假设您有一个数组,第i个元素是第i天给定股票的价格。
设计算法以找到最大的利润。您最多可以完成两次交易。
请注意,无法同时进行多项交易(即必须先出售股票才能再次购买)
输入
多组输入数据
每组数据第一行一个数n,(1≤n≤105)
接下来一行n个数表示股票的价格(1≤ai≤109)
输出
每组数据一行一个数
输入样例
1 | 5 |
输出样例
1 | 4 |
AC代码
1 |
|
分析
我们还是延续思路继续分析,本题是要求利润最大并且只能完成两次交易,那我们还是同样分析,因为有两次交易,所以需要4个变量来存,第一次买了之后当天的总收益为-a[i](因为相当于之前没有卖出),然后第一次卖了之后当天的总收益为buy1-a[i](因为之前是处于第一次买了之后的状态所以用buy1来减),然后第二次买了之后当天的总收益为sell1-a[i](因为相当于之前有一次卖出),然后第二次卖了之后当天的总收益为buy2-a[i](因为之前是处于第二次买了之后的状态所以用buy2来减),然后我们考虑每一天的情况即可。
转移方程
- buy1=max(buy1,-a[i]);
- sell1=max(sell1,buy1+a[i]);
- buy2=max(buy2,sell1-a[i]);
- sell2=max(sell2,buy2+a[i]);
HINT
还是一样需要注意数据类型的选择和sell1、buy1、buy2的初始赋值,然后是sell1最初值置0才能保证第一次买后总收益的正确性。然后是对方程的理解,是怎么样实现的。
股票Ⅳ
题面
假设您有一个数组,第i个元素是第i天给定股票的价格。
设计算法以找到最大的利润。您最多可以完成k次交易。
请注意,无法同时进行多项交易(即必须先出售股票才能再次购买)
输入
多组输入数据
每组数据第一行两个数n,k,(1≤n,k≤103)
接下来一行n个数表示股票的价格(1≤ai≤109)
输出
每组数据一行一个数
输入样例
1 | 5 2 |
输出样例
1 | 4 |
AC代码
1 |
|
分析
我们还是相同思路继续分析,本题是要求利润最大并且只能完成k次交易,因为有k次交易,所以需要2k个变量来存,即用两个数组来存即可,第一次买了之后当天的总收益为-a[i](因为相当于之前没有卖出),然后第一次卖了之后当天的总收益为buy[1]-a[i](因为之前是处于第一次买了之后的状态所以用buy[1]来减),然后第二次买了之后当天的总收益为sell[1]-a[i](因为相当于之前有一次卖出),然后第二次卖了之后当天的总收益为buy[2]-a[i](因为之前是处于第二次买了之后的状态所以用buy[2]]来减),然后用一个从2-k的循环来实现此过程即可。
转移方程
- buy[j]=max(buy[j], sell[j-1]-a[i])
- sell[j]=max(sell[j], buy[j]+a[i])
HINT
还是一样需要注意数据类型的选择和buy[],sell[]的初始赋值,然后是上文的AC代码的循环其实不用把buy[1]、sell[1]单独拿出来讨论的,只是更方便理解。
v1.5.2