45.跳跃游戏II - 双指针+贪心+动态规划完美解决

「爱情、让人受尽委屈。」 2024-03-26 15:07 118阅读 0赞

![在这里插入图片描述][1a65eb27297040c4a42815b52e65c2bf.png]  
这个题目第一眼看上去，就试图用回溯法+剪枝  
一步步走，把所有方案走一遍，看哪个步数最少。

class Solution {
        
        public int jump(int[] nums) {
        
            min = nums.length;
            find(nums,0,0);
            return min;
    
        }
        // 当前元素序列号为k，共跳跃了index次
        public void find(int[] nums, int index, int k) {
        
            // 若已经比min长了，或者当前元素已经越界，那就别再尝试了
            if(index>=min|| k >= nums.length){
        
                return;
            }
            if(k == nums.length-1){
        
                min = Math.min(min,index);
                return;
            }
            if(nums[k] + k >= nums.length-1){
        
                min = Math.min(min,index+1);
                return;
            }
            for(int i=nums[k];i>0;i--){
        
                find(nums,index+1,k+i);
            } 
        }
    
        private int min;
    }

很快做了出来，但是不出意料的超时了。  
于是尝试用动态规划。

1.  定义do\[i\]  
    定义一个dp\[i\]，表示到i元素时，跨的最少步数。
2.  状态转移方程  
    那我dp\[i\]和dp\[i-1\]有直接关系吗？有，但是如果要转换为数学公式关系会很复杂。  
    每次找到跨最大的那一步，先是想到了倒退着找，倒着试图找最远一个能跨到元素i的是哪一个，假设是j，那就是dp\[i\]=dp\[j\]+1。  
    但是倒退着找会有一个边界，你要找到第一个跨不到的元素，然后+1才是该元素，这又会衍生出一些边界问题。  
    倒退不行，那我就傻瓜一点，每次都从0往后正着找，找到第一个刚好能一步跨到元素i的元素，那就是j。肯定是最优解。  
    dp\[i\] = dp\[j\]+1, j是从0开始第一个能跨到i的元素，即nums\[j\]+j>=i
3.  初始化  
    dp\[0\]=0 后面才开始跨步子

class Solution {
        
        public int jump(int[] nums) {
        
            // dp[i]表示到i元素时最少跳跃次数，从0开始依次找到距离i最远但是可以一步到达的元素j
            // dp[i] = dp[j]+1, j从0开始第一个刚好一步就到达i元素
            int[] dp = new int[nums.length];
            dp[0]=0;
            int j;
            for(int i=1;i<nums.length;i++){
        
                j=0;
                while(j+nums[j]<i){
        
                    j++;
                }
                dp[i]=dp[j]+1;
            }
            return dp[nums.length-1];
        }
    }

在每个循环中，我都把j重置为了0，这明显很耗效率，于是我思考了下，能不能优化。  
如果遍历到了i，那dp\[i-1\]已经找了最远能跨到自己的元素 j 1 j\_\{1\} j1,那这个时候直接用 j 1 j\_\{1\} j1开始找，因为0～ j 1 j\_\{1\} j1元素之间的元素肯定不是dp\[i\]的最远跨到元素j,如果是的话，那它肯定是dp\[i-1\]的最优解。矛盾。  
故不需要从0开始起步，直接用上一个j即可，优化了一下

class Solution {
        
        public int jump(int[] nums) {
        
            // dp[i]表示到i元素时最少跳跃次数，从0开始依次找到距离i最远但是可以一步到达的元素j
            // dp[i] = dp[j]+1, j从0开始第一个刚好一步就到达i元素
            int[] dp = new int[nums.length];
            dp[0]=0;
            int j=0;
            for(int i=1;i<nums.length;i++){
        
                while(j+nums[j]<i){
        
                    j++;
                }
                dp[i]=dp[j]+1;
            }
            return dp[nums.length-1];
        }
    }

![在这里插入图片描述][758e04ad6805450c92aee842f7d2a37d.png]  
这题很经典，不同于一般的动规转移方程，说明不能硬套公式，需要灵活使用，使用了双指针+贪心+动态规划。

[1a65eb27297040c4a42815b52e65c2bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ea479b82a70844f2b7ac1dac6d18e323.png
[758e04ad6805450c92aee842f7d2a37d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/cfe40d72d3f048efb0b7d7705fbd621d.png