LintCode第116题-跳跃游戏
描述
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置
样例 1：
输入：
A = [2,3,1,1,4]输出：
true解释：
0 -> 1 -> 4（这里的数字为下标）是一种合理的方案。
样例 2：
输入：
A = [3,2,1,0,4]输出：
false解释：
不存在任何方案能够到达终点。
挑战
这个问题有两个方法，一个是贪心和 动态规划。
贪心方法时间复杂度为O(N)。
动态规划方法的时间复杂度为为O(n2)。
思路:题目明确说使用贪心和动态规划
先来看动态规划
本质上动态规划本质上就是“把数学里的递推（递推式/递归关系）工程化并高效求解”
动态规划的四要素
1.状态dp[i]//注意 这里题目说的是否能到达数组的最后一个位置 没有说从哪个点至哪个点是否可以到达 所以状态就是dp[i] 无需二维数组
2.状态转移方程dp[i]=dp[j]&&a[j]>=(i-j) 其中 i>=j
3.状态初始条件 dp[0]=true
4.边界条件/遍历顺序/答案 i 从小到大，j 在 [0, i-1] dp[n-1];
代码如下:
public class Solution {
/**
* @param a: A list of integers
* @return: A boolean
*/
public boolean canJump(int[] a) {
// write your code here
// 状态 dp[i]
//状态转移dp[i]=dp[i-1]&&(a[j]>=(j-i));//a[j]的长度指的是跳跃的最大长度i>=1 i代表其实位置 j代表终点的位置
// 初始化 dp[0]=true;
//边界条件i>=0 && i<a.length
if (a == null || a.length == 0)
{
return false;
}
int n = a.length;
boolean[] dp=new boolean[n];
dp[0]=true;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(dp[j]&&(a[j]>=(i-j)))
{
dp[i]=true;
break;
}
}
}
return dp[n-1];
}
}
动态规划的时间复杂度为O(n²)
如果使用贪心法
极值 + 不变量:每到一个可达位置 i，就把“最远可达”推到 i+a[i] 的极值；不变量“最远可达下标”单调不减。
单调结构:可达区间像一段区间覆盖不断右扩，满足贪心所需的单调性
尤其是遇到单调+极值的组合 易想到贪心法的实现
代码如下:
public class Solution {
/**
* @param a: A list of integers
* @return: A boolean
*/
//贪心法
public boolean canJump(int[] a) {
int n=a.length;
if(a==null||a.length==0) //边界条件
{
return false;
}
int farthest = 0;
for(int i=0;i<n;i++)
{
if (i > farthest) return false; // 连 i 都到不了，后面更到不了
farthest = Math.max(farthest, i + a[i]); // 扩展最远可达 关键是当前的下标位置+可跳的步数i + a[i] 注意不是累加步数 贪心法的体现 当前最优的局部选择 每步把可达的覆盖区间右端推到当前能达到的最远位置
if (farthest >= n - 1)
{
return true; // 已覆盖到终点
}
}
return farthest >= n - 1;
}
}
贪心法的时间复杂度为O(n)