122.买卖股票的最佳时机 II

之前用贪心写过这题

int maxProfit(vector<int>& prices) {
	vector<int> dp(prices.size(), 0);
	int curVal = prices[0];

	for (int i = 1; i < prices.size(); ++i) {
		if (prices[i] < curVal)
			dp[i] = dp[i - 1];
		else
			dp[i] = dp[i - 1] + prices[i] - curVal;
		curVal = prices[i];
	}
	return dp[prices.size() - 1];
}

// 用滚动数组思路进行写法优化（完全变成了之前的贪心写法）
int maxProfit(vector<int>& prices) {
	int dp = 0;
	int curVal = prices[0];

	for (int i = 1; i < prices.size(); ++i) {
		if (prices[i] > curVal)
			dp += prices[i] - curVal;
		curVal = prices[i];
	}
	return dp;
}

延续 买卖股票I 思路的动规写法：

与 I 相比，差异在于可以反复买入卖出，即每次买入时的启动资金不是0，而是之前卖出所得的资金总量

差异仅在于dp[i][0]的递推公式：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])

int maxProfit(vector<int>& prices) {
	vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
	dp[0][0] = -prices[0];

	for (int i = 1; i < prices.size(); ++i) {
		// 是否选择今天买入
		dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
		// 是否选择今天卖出
		dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
	}
	return dp[prices.size() - 1][1];
}