目录Problem: 122. 买卖股票的最佳时机 II
思路
仍然是一道比较简单的动态规划,但是一上手做还是没理清楚状态是什么。一天的状态只有两种,持有股票和没有股票,这样就可以列出状态转移方程\(dp[i][j]=max(dp[i-1][j],dp[i-1][j*]+或-price[i])\), 这里的j表示有无股票,j*表示从另一种状态转移到这种状态
解题方法
开dp[n][2]的数组,dp[i][0]表示没有股票, dp[i][1]表示有股票,这里和背包不同的是需要注意dp[i-1][0]到dp[i][1]需要-price[i],反过来需要+price[i]
复杂度
时间复杂度:
\(O(n)\)
空间复杂度:
\(O(2n)\)
Code
//这里是第一种解法
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int dp[n][2];
dp[0][0]=0;
dp[0][1]=-prices[0];
for (size_t i = 1; i < n; 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[n-1][0];
}
};
//这里稍作优化,其实可以发现动态规划中这一行的数据只和上一行有关系,所以直接省略之前的储存
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int precash=0,prestock=-prices[0];
int cash=0,stock=0;
for (size_t i = 1; i < n; i++)
{
cash=max(precash,prestock+prices[i]);
stock=max(prestock,precash-prices[i]);
precash=cash;
prestock=stock;
}
return cash;
}
};
标签:int,max,复杂度,122,leecode,prices,动态,dp,size
From: https://www.cnblogs.com/oxidationreaction/p/17978490