买卖股票的最佳时机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;}
};
