把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！122.买卖股票的最佳时机II
题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）
思路
这道题使用贪心算法思路为：把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！
将数据画成折现图
根据图中可以很明显看出我们只收集正利润即可 。得到的数组如下。
局部最优：收集每天的正利润，全局最优：求得最大利润。
代码
1 // 贪心思路
2 class Solution {
3 public int maxProfit(int[] prices) {
4 int result = 0;
5 for (int i = 1; i < prices.length; i++) {
6 result += Math.max(prices[i] - prices[i - 1], 0);
7 }
8 return result;
9 }
1 class Solution { // 动态规划
2 public int maxProfit(int[] prices) {
3 // [天数][是否持有股票]
4 int[][] dp = new int[prices.length][2];
5
6 // base case
7 dp[0][0] = 0;
8 dp[0][1] = -prices[0];
9
10 for (int i = 1; i < prices.length; i++) {
11 // dp公式
12 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
13 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
14 }
15
16 return dp[prices.length - 1][0];
17 }
18 }
55. 跳跃游戏
题目链接：55. 跳跃游戏 - 力扣（LeetCode）
思路
这道题关键在于可跳的范围，我们不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
可以参考下图方便理解。
代码
1 class Solution {
2 public boolean canJump(int[] nums) {
3 if (nums.length == 1) {
4 return true;
5 }
6 //覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
7 int coverRange = 0;
8 //在覆盖范围内更新最大的覆盖范围
9 for (int i = 0; i <= coverRange; i++) {
10 coverRange = Math.max(coverRange, i + nums[i]);
11 if (coverRange >= nums.length - 1) {
12 return true;
13 }
14 }
15 return false;
16 }
17 }
45.跳跃游戏II
题目链接：45. 跳跃游戏 II - 力扣（LeetCode）
思路
这道题贪心的思路为：局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。
解题时从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！
这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
图中覆盖范围的意义在于，只要红色的区域，最多两步一定可以到！（不用管具体怎么跳，反正一定可以跳到）
代码
方法一
1 // 版本一
2 class Solution {
3 public int jump(int[] nums) {
4 if (nums == null || nums.length == 0 || nums.length == 1) {
5 return 0;
6 }
7 //记录跳跃的次数
8 int count=0;
9 //当前的覆盖最大区域
10 int curDistance = 0;
11 //最大的覆盖区域
12 int maxDistance = 0;
13 for (int i = 0; i < nums.length; i++) {
14 //在可覆盖区域内更新最大的覆盖区域
15 maxDistance = Math.max(maxDistance,i+nums[i]);
16 //说明当前一步，再跳一步就到达了末尾
17 if (maxDistance>=nums.length-1){
18 count++;
19 break;
20 }
21 //走到当前覆盖的最大区域时，更新下一步可达的最大区域
22 if (i==curDistance){
23 curDistance = maxDistance;
24 count++;
25 }
26 }
27 return count;
28 }
29 }
方法二
1 // 版本二 （版本一的简化）
2 class Solution {
3 public int jump(int[] nums) {
4 int result = 0;
5 // 当前覆盖的最远距离下标
6 int end = 0;
7 // 下一步覆盖的最远距离下标
8 int temp = 0;
9 for (int i = 0; i <= end && end < nums.length - 1; ++i) {
10 temp = Math.max(temp, i + nums[i]);
11 // 可达位置的改变次数就是跳跃次数
12 if (i == end) {
13 end = temp;
14 result++;
15 }
16 }
17 return result;
18 }
19 }
标签：游戏,nums,int,II,prices,length,跳跃,覆盖范围,dp From： https://www.cnblogs.com/xpp3/p/17178285.html