【LeetCode】55. Jump Game

问题描述

https://leetcode.com/problems/jump-game/#/description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

算法分析

动态规划

设f(i)为在i位置能到达的最大位置：

f(0) = nums[0]
f(i) = max(f(i-1), i+nums[i]), f(i-1)>=i
     = 0, f(i-1)<i ，此时可直接return false

最后若f(nums.length-2)>nums.length-1，则返回true；否则，返回false。

代码

public boolean canJump(int[] nums) {
	    	if(nums.length==0) return false;
	    	if(nums.length==1) return true;
	    	int[] f = new int[nums.length];
	    	f[0] = nums[0];
	    	for(int i=1;i<nums.length;i++) {
	    		if(i<=f[i-1]) {
	    			f[i] = Math.max(f[i-1], i+nums[i]);
	    		} else {
	    			return false;
	    		}
	    	}
	    	return f[nums.length-2]>=nums.length-1;
	    }

LeetCode解题代码仓库：https://github.com/zgljl2012/leetcode-java