买卖股票的最佳时机II

贪心思路

要想使用贪心算法解决此问题，意识到利润是可分解的很关键。比如[1,2,3,4,5]这个输入，最大利润为第一天买入，第五天卖出。这等效于第一天买入，第二天卖出，第二天再买入。。。
prices[4] - prices[0] = (prices[1] - prices[0]) + (prices[2] - prices[1]) + (prices[3] - prices[2]) + (prices[4] - prices[3])
所以总利润的最大值等于所有头天买第二天卖的正利润之和，局部最优组成了全局最优，可以用贪心算法。

class Solution{
public:
	int maxProfit(vector<int>& prices){
		int result = 0;
		for(int i = 1; i < prices.size(); i++){
			result += max(prices[i] - prices[i - 1], 0);
		}
		return result;
	}
};

动态规划思路

每一天的操作要么买入要么卖出，在该天要么持有股票，要么不持有股票。
设dp[i][0]代表在第 i 天持有股票后的最大利润，dp[i][1]代表在第 i 天不持股的最大利润。

class Solution{
public:
	int maxProfit(vector<int>& prices){
		int n = prices.size();
		vector<vector<int>> dp(n, vector<int>(2, 0));
		dp[0][0] -= prices[0];
		for(int i = 1; i < n; i++){
			// 在第i - 1天持有股票的最大利润和第i - 1天没持股第i天买入之中选择最大值
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
			// 在第i - 1天不持股的最大利润和第i - 1天持股第i天卖出之中选择最大值 
			dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
		}
		return dp[n - 1][1];
	}
};

跳跃游戏

怎么跳不是问题，重点在于能跳的范围，范围内的每一点都能到达！
贪心算法局部最优解：每次取最大可跳步数，更新最远可跳范围。全局最优解：得到整体最远范围，看能否覆盖终点。

class Solution{
public:
	bool canJump(vector<int>& nums){
		int cover = 0;
		for(int i = 0; i <= cover; i++){  // 注意是小于等于能到达的范围
			cover = max(cover, i + nums[i]);
			if(cover >= nums.size() - 1)  return true;  // 如果能到达的范围已经覆盖了终点，返回true
		}
		return false;  // 到不了终点
	}
};

跳跃游戏II

与上一道题相似，也是通过跳跃的覆盖范围来判断是否需要走一步。贪心的局部最优策略是让当前可跳的覆盖范围尽量大，如果覆盖范围没到终点，步数就+1，全局最优就做到了以最小的步数增大覆盖范围。这道题需要统计两个覆盖范围，一个是当前这一步的最大覆盖和下一步的最大覆盖。
如果下标到达了当前这一步的最大覆盖位置，还没到终点的话，那么就必须再走一步来增大覆盖范围，直到覆盖范围能覆盖终点。

class Solution{
public:
	int jump(vector<int>& nums){
		int result = 0;  // 统计步数
		if(nums.size() == 1)  return result;
		int curCover = 0;  // 当前步的最大覆盖
		int nextCover = 0;  // 下一步能达到的最大覆盖
		for(int i = 0; i < nums.size(); i++){
			nextCover = max(nextCover, i + nums[i]);  // 求下一步能到的最大覆盖范围
			if(i == curCover){  // 到达当前步的最大覆盖位置
				result++;  // 需要往前走一步
				curCover = nextCover;  // 更新覆盖范围
				if(curCover >= nums.size() - 1)  break;  // 如果新的覆盖范围已经覆盖了终点，结束循环
				// 避免在for循环中i=nums.size()-1 && i==curCover，又对result+1
			}
		}
		return result;
	}
};

代码可以再简洁一些，因为题目中说了给的数组是一定能跳到终点的。所以可以调整 for 循环的终止位置，只到nums.size() - 2即可。这样不会抵达终点，当抵达当前最大覆盖时，必须往前走一步，不需要另外判断下一步是否已经覆盖终点。

class Solution{
public:
	int jump(vector<int>& nums){
		int result = 0;
		if(nums.size() == 1)  return result;
		int curCover = 0;
		int nextCover = 0;
		for(int i = 0; i < nums.size() - 1; i++){
			nextCover = max(nextCover, i + nums[i]);
			if(i == curCover){  // 已经到达了当前的最大覆盖
				result++;
				curCover = nextCover;
			}
		}
		return result;
	}
};