121. 买卖股票的最佳时机
这道题还是挺简单的，一下子就做出来的。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> dp(prices.size(),0);
int min_price = prices[0];
for(int i=1; i<prices.size(); i++){
if(prices[i] < min_price){
min_price = prices[i];
}
dp[i] = max(dp[i-1],prices[i]-min_price);
}
return dp[prices.size()-1];
}
};
今天是3月6号。本来之前只是用贪心算法写出来了。后来发现好多类似的题得用动态规划，那么这道题我就重新用动态规划写一遍。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(2));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i=1; i<prices.size(); i++){
dp[i][0] = max(dp[i-1][0],-prices[i]);//持有
dp[i][1] = max(dp[i-1][1],prices[i]+dp[i-1][0]);//不持有
}
return max(dp[prices.size()-1][0],dp[prices.size()-1][1]);
}
};
用动态规划的写法里，我们记录每个index的两个数据。dp[i][0]是当天持有股票所得的现金，dp[i][1]是当天不持有股票所得的现金。
dp[i][0]是根据什么算出来的呢？有两种情况：
- 我们向来就持有了股票，那么我们就去前一天的值就可以了：dp[i-1][0]
- 我们今天（也就是第i天)刚买这个股票，那么我们目前的钱数就应该是-price。
dp[i][0]也有两种情况需要考虑：
- 我们早就不持有股票了，那么我们就取前一天的值就行了：dp[i-1][1]
- 我们今天才抛售股票，那么我们的钱数就应该是昨天持有股票时的签署加上今天的价格，就是我们的获利。那就是prices[i]+dp[i-1][0]
想明白这个其实也不太容易，而且需要记住。
122.买卖股票的最佳时机II
使用贪心算法算出来的。（之前做过这道题）
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
int min_sum = prices[0];
for(int i=1; i<prices.size(); i++){
if(prices[i] > min_sum){
result += prices[i] - min_sum;
}
min_sum = prices[i];
}
return result;
}
};
这道题我也按照动态规划的写法写了一遍。唯一的区别的就是对于持有股票状态的每天，不应该是单纯的-price，而是前一天没有股票的状态的钱数减去今天股票的钱数，这代表着今天又买了股票。之所以做这个改变，是因为这道题我们可以再次购买股票。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(len,vector<int>(2));
dp[0][0] = -prices[0];
dp[0][1] = 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 max(dp[len-1][0],dp[len-1][1]);
}
};
