leetcode 55. Jump Game | 55. 跳跃游戏（暴力递归-＞傻缓存-＞DP）

清疚 2022-09-14 09:25 162阅读 0赞

## 题目 ##

[https://leetcode.com/problems/jump-game/][https_leetcode.com_problems_jump-game]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

又是经典套路，暴力递归->傻缓存->DP

没写草稿，直接看代码吧

class Solution { 
        public boolean canJump(int[] nums) { 
            // 【Solution 1】暴力递归
    // return process1(0, nums);
    
            // 【Solution 2】傻缓存
    // return process2(0, nums, new int[nums.length]);
    
            // 【Solution 3】自底向上的dp
            boolean[] dp = new boolean[nums.length];
            dp[nums.length - 1] = true;
            for (int i = nums.length - 2; i >= 0; i--) { 
                for (int j = 1; j <= nums[i]; j++) { 
                    if (i + j >= nums.length - 1) { 
                        dp[i] = true;
                        break;
                    }
                    if (dp[i + j]) { 
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[0];
        }
    
        // 【Solution 2】dp数组含义: 0=未知 1=true -1=false
        public boolean process2(int i, int[] nums, int[] dp) { 
            if (i >= nums.length - 1) return true;
            if (dp[i] != 0) return dp[i] == 1;
    
            for (int j = 1; j <= nums[i]; j++) { 
                if (process2(i + j, nums, dp)) { 
                    dp[i] = 1;
                    return true;
                }
            }
            dp[i] = -1;
            return false;
        }
    
        // 【Solution 1】递归含义：从i位置开始跳，能不能到终点？
        public boolean process1(int i, int[] nums) { 
            if (i >= nums.length - 1) return true;
            for (int j = 1; j <= nums[i]; j++) { 
                if (process1(i + j, nums)) return true;
            }
            return false;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_jump-game]: https://leetcode.com/problems/jump-game/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b1705f52f08848aa9b6573b2868f3898.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/ac2fdb12889140cb806a1d782faa7450.png