本文主要是介绍day32 第八章 贪心算法 part02● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一遍过。如果一开始第二个元素比第一个元素小，就选择第二个元素开始，这样买入价低，反之则是加上第二个元素和第一个元素的差价，并从第二个元素开始，比较第三个元素和第二个元素的相对大小关系。
class Solution {
public:int maxProfit(vector<int>& prices) {int total=0;int res=0;int st=prices[0];int ma=0;int mi=0;for(int i=1;i<prices.size();i++){if(prices[i]>st){mi=prices[i]-st;res+=mi;st=prices[i];}else{st=min(st,prices[i]);}}return res;}
}; 如果想到其实最终利润是可以分解的，那么本题就很容易了！
如何分解呢？
假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
题解的方法：更简洁。
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;}
}; 
一遍过。当前能走多远，就说明能覆盖多大范围。范围内的可以继续走当前数表示的步数，得到最大覆盖范围。如果走完了最大覆盖范围，仍旧没走到数组末，那么就是false，反之true。
class Solution {
public:bool canJump(vector<int>& nums) {int len=nums.size();int res=0;for(int i=0;i<=res;i++){res=max(i+nums[i],res);if(res>=len-1) return true;}return false;}
};
看了题解。
贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。
思路虽然是这样，但在写代码的时候还不能真的能跳多远就跳多远，那样就不知道下一步最远能跳到哪里了。
所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！
这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
必须要从开头开始跳。
class Solution {
public:int jump(vector<int>& nums) {int len=nums.size();if(nums.size()==1) return 0;int cur=0;int ans=0;int next=0;for(int i=0;i<len;i++){next=max(next,i+nums[i]);if(i==cur){ans++;cur=next;if(next>=len-1){break;}}}return ans;}
};另一种思路：
针对于方法一的特殊情况，可以统一处理，即：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。想要达到这样的效果，只要让移动下标，最大只能移动到 nums.size - 2 的地方就可以了。
因为当移动下标指向 nums.size - 2 时：
-
如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：
// 版本二
class Solution {
public:int jump(vector<int>& nums) {int curDistance = 0; // 当前覆盖的最远距离下标int ans = 0; // 记录走的最大步数int nextDistance = 0; // 下一步覆盖的最远距离下标for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标if (i == curDistance) { // 遇到当前覆盖的最远距离下标curDistance = nextDistance; // 更新当前覆盖的最远距离下标ans++;}}return ans;}
};其精髓在于控制移动下标 i 只移动到 nums.size() - 2 的位置，所以移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不用考虑别的了。
这篇关于day32 第八章 贪心算法 part02● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
