121 买卖股票的最佳时机
思路：我们用 dp[i][0] 表示在第 i 天结束时，持有一支股票所能获得的最大利润，用 dp[i][1] 表示在第 i 天结束时，不持有股票所能获得的最大利润。
根据题目要求，我们可以进行多次交易，因此在任何一天结束时，我们都有两种选择：卖出股票或者不进行任何操作。如果在第 i 天卖出股票，那么我们之前一定持有一支股票，因此需要从 dp[i-1][0] 转移而来。如果在第 i 天不进行任何操作，那么我们可能之前也没有持有股票，也可能之前持有了一支股票但是在第 i 天卖掉了，因此需要从 dp[i-1][1] 转移而来。
对于 dp[i][0]，我们可以从 dp[i-1][0] 转移而来，表示不进行任何操作；也可以从 dp[i-1][1] 减去 prices[i] 转移而来，表示在第 i 天购买了一支股票。
对于 dp[i][1]，我们可以从 dp[i-1][1] 转移而来，表示不进行任何操作；也可以从 dp[i-1][0] 加上 prices[i] 转移而来，表示在第 i 天卖出了股票。
最终，我们需要返回 dp[len-1][1]，表示在最后一天结束时，不持有股票所能获得的最大利润。
1.动态规划
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if(len == 0) return 0;
vector<vector<int>> dp(len, vector<int>(2));
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], prices[i] + dp[i - 1][0]);
}
return dp[len - 1][1];
}
};
122 买卖股票的最佳时机 II
思路：在第一天，持有股票可以获得的最大利润被设置为当前股票价格的相反数，而卖出股票可以获得的最大利润被设置为0（因为此时还没有股票可卖）。
然后，对于每一天，持有股票可以获得的最大利润被更新为前一天最大持股利润和在当天买入股票可以获得的利润（即前一天最大卖出利润减去当天股票价格）的最大值。同样地，卖出股票可以获得的最大利润被更新为前一天最大卖出利润和在当天卖出股票可以获得的利润（即前一天最大持股利润加上当天股票价格）的最大值。
最后，返回最后一天可以获得的最大利润（即完成所有交易后的利润）作为解。
1.动态规划
class Solution {
public:
int maxProfit(vector<int>& prices) {
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] = 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[len - 1][1];
}
};
