买卖股票的最大利润II——动态规划、贪心

买卖股票的最大利润II——动态规划、贪心 题目描述：

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

解法一：动态规划

代码1：

int maxProfit(vector& prices) {
    int n=prices.size();
    vector>dp(n,vector(2));//dp[i][0]表示没有股票时手里的钱，dp[i][1]有票
    dp[0][0]=0;dp[0][1]=-prices[0];//买票借钱
    for(int i=1;i 
注意到上面的状态转移方程中，每一天的状态只与前一天的状态有关，而与更早的状态都无关，因此我们不必存储这些无关的状态，只需要将 dp[i−1][0] 和 dp[i−1][1] 存放在两个变量中，通过它们计算出 dp[i][0] 和 dp[i][1] 并存回对应的变量，以便于第 i+1天的状态转移即可。
 
精简代码1：
 
int maxProfit2(vector& prices) {
    int n=prices.size();
    int a=0,b=-prices[0];
    for(int i=1;i 
方法二：贪心算法 
 
 
因为交易次数不受限，如果可以把所有的上坡全部收集到，一定是利益最大化的。
 
 
同一天可以买卖同一支股票任意次，只有你玩的乐意。当然没必要，只要把所有的上坡买下就是利益最大化。
 
 
代码2：  
 
//贪心算法  将所有的上升阶段全部买下
int maxProfit(vector& prices) {
    int n=prices.size();
    int ans=0;
    for(int i=1;iprices[i-1])
            ans+=prices[i]-prices[i-1];
    }
    return ans;
}
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5711392.html