參考資料：

https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html

122. 買賣股票的最佳時機 II

題目描述：

給你一個整數數組?prices?，其中?prices[i]?表示某支股票第?i?天的價格。

在每一天，你可以決定是否購買和/或出售股票。你在任何時候?最多?只能持有?一股?股票。你也可以先購買，然后在?同一天?出售。

返回?你能獲得的?最大?利潤?。

示例 1：

輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 。隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6 - 3 = 3 。總利潤為 4 + 3 = 7 。

思路分析：

? ? ? ? 貪心思路：每天只取正利潤

代碼實現：

class Solution {//差分數組public int maxProfit(int[] prices) {//可以理解為：最大的盈利就是將所有正值相加int len=prices.length;if(len==0 || len==1) return 0;int[] diff=new int[len];diff[0]=prices[0];for(int i=1;i<len;i++){diff[i]=prices[i]-prices[i-1];}int res=0;for(int i=1;i<len;i++){//差分數組中大于0的就是盈利的值if(diff[i]>0) res+=diff[i];}return res;}//動規 //對比 買賣股票1，只有dp[i][0]的遞推公式改變// public int maxProfit(int[] prices) {//     // if (prices == null || prices.length == 0) return 0;//     int len=prices.length;//     int[][] dp=new int[len][2];//     //dp[i][0]:第i天 不持有 這個股票的max金額//     //dp[i][1]:第i天 持有 這個股票的max金額//     dp[0][0]=0;//     dp[0][1]=-prices[0];//     for(int i=1;i<len;i++){//         dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);//-prices[i]變為dp[i-1][1]-prices[i]//         dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);//     }//     //一定是最后一天不持有股票的金額 > 仍持有//     return dp[len-1][0];// }
}

55. 跳躍游戲

題目描述：

給你一個非負整數數組?nums?，你最初位于數組的?第一個下標?。數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個下標，如果可以，返回?true?；否則，返回?false?。

示例?1：

輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標。

思路分析：

? ? ? ? 記錄每一個能覆蓋到的最大范圍，能覆蓋到結尾就返回

代碼實現：

class Solution {//覆蓋范圍//局部最優，每個元素最大的覆蓋范圍——>全局最優，總共最大的覆蓋范圍public boolean canJump(int[] nums) {if(nums.length==1) return true;int cover=0;for(int i=0;i<=cover;i++){cover=Math.max(cover,i+nums[i]);if(cover>=nums.length-1) return true;}return false;}
}

?45. 跳躍游戲 II

題目描述：

給定一個長度為?n?的?0 索引整數數組?nums。初始位置為?nums[0]。

每個元素?nums[i]?表示從索引?i?向前跳轉的最大長度。換句話說，如果你在?nums[i]?處，你可以跳轉到任意?nums[i + j]?處:

• 0 <= j <= nums[i]?
• i + j < n

返回到達?nums[n - 1]?的最小跳躍次數。生成的測試用例可以到達?nums[n - 1]。

示例 1:

輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2。從下標為 0 跳到下標為 1 的位置，跳?1步，然后跳?3?步到達數組的最后一個位置。

思路分析：

記錄當前覆蓋范圍里的下一個最大覆蓋范圍，

?如果下一覆蓋范圍到結尾就res++,break

?如果當前覆蓋走到尾了，記錄的下一個覆蓋范圍也未到尾，則進入下一個覆蓋范圍繼續搜索,res++

代碼實現：

class Solution {public int jump(int[] nums) {if(nums.length==1) return 0;int cur=0;//當前cover的最遠下標int next=0;//下一個覆蓋范圍int res=0;for(int i=0;i<nums.length;i++){next=Math.max(next,i+nums[i]);//記錄當前覆蓋范圍中的下一覆蓋范圍maxif(next>=nums.length-1){//調到下一個覆蓋范圍即可res++;break;}if(i==cur){//當前覆蓋范圍走到盡頭了也沒到結尾，要進入下一個覆蓋范圍cur=next;res++;//跳進下一個覆蓋范圍}}return res;}
}