121. 買賣股票的最佳時機

class Solution {
public:int maxProfit(vector<int>& prices) {// int res =0 ;// int low = INT_MAX;// for (int i = 0; i < prices.size(); i++) {//     low = min(low, prices[i]);//     res = max(res, prices[i]-low);// }// return res;// 動態規劃方法int len = prices.size();if (len == 0) return 0;vector<vector<int>> dp(len, vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {// 持有股票dp[i][0] = max(dp[i-1][0], -prices[i]);// 不持有股票dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);}return dp[len-1][1];}
};

122. 買賣股票的最佳時機 II

class Solution {
public:int maxProfit(vector<int>& prices) {// 貪心// int res = 0;// for (int i = 1; i<prices.size(); i++) {//     if (prices[i]-prices[i-1] > 0){//         res += prices[i] - prices[i-1];//     }// }// 動態規劃int len = prices.size();vector<vector<int>> dp(len, vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {// dp[i][0]表示第i天持有股票的最大現金dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]);// dp[i][1]表示第i天不持有股票的最大現金dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);}return dp[len-1][1];// return res;}
};

最近忙于考研復試準備，沒有時間寫總結，同時學習深度肯定是不夠的。股票問題I和II都可以用貪心和動態規劃來解決，注意總結記憶。