0x055 跳跃游戏

https://leetcode-cn.com/problems/jump-game/

思路：

1、maxJump记录当前点可达的最远距离

2、从后往前遍历

• 当nums[i] i >= maxJump时，更新最远距离maxJump

3、若最后能够抵达0，则表示可以从0达到n

public static boolean canJump(int[] nums) { int n = nums.length; int maxJump = n - 1; for (int i = n - 2; i >= 0; i--) { if (nums[i] i >= maxJump) { maxJump = i; } } return maxJump == 0; } 代码【动态规划】

思路：采用与贪心一样的思路

1、构建表：dp[i]表示当前位置i可达的最远位置

2、初始化：p[n-1]=1

3、填充方向：从后往前

4、状态转移：maxJump = i nums[i]

• 更新可达范围[i 1， maxJump]内的值

public static boolean canJump(int[] nums) { int n = nums.length; int[] dp = new int[n]; dp[n - 1] = 1; for (int i = nums.length - 2; i >= 0; i--) { int maxJump = Math.min(i nums[i], nums.length - 1); for (int j = i 1; j <= maxJump; j ) { if (dp[j] == 1) { dp[i] = 1; break; } } } return dp[0] == 1; } 代码【递归】

思路：与动态规划相似

1、递归出口：dp[idx]==1 || dp[idx]==-1

2、递归流程：

• 先考虑当前maxJump = idx nums[idx]
• i从idx 1到maxJump
• 若jump(nums, dp, i)可达，则更新dp[idx]

public boolean canJump(int[] nums) { int n = nums.length; int[] dp = new int[n]; dp[n - 1] = 1; return jump(nums, dp, 0); } private boolean jump(int[] nums, int[] dp, int idx) { if (dp[idx] == 1) { return true; } else if (dp[idx] == -1) { return false; } int maxJump = Math.min(idx nums[idx], nums.length - 1); for (int i = idx 1; i <= maxJump; i ) { // notes: [idx 1, maxJump] if (jump(nums, dp, i)) { dp[idx] = 1; return true; } } dp[idx] = -1; return false; }