55.跳跃游戏

LeetCode

动态规划详解

确定状态

最后一步

考虑青如果能跳到最后一个位置,

那必须满足这样的关系：

• 如果是从位置上跳过来，必须能先跳到位置

• 位置上表示的步数大小必须大于或等于从到最后位置,即

子问题

把能否跳到位置的问题，转化位能否跳到位置的问题

且 问题规模缩小

状态

最终可以确定状态： 表示能否到最后位置

转移方程

• 通过最后一步的分析, 位置必须能到达，且位置 的步数与位置的和必须大于等于最后位置的索引 ,所以有

• 如何找到 是通过循环 ,只要可以找到一个满足的条件，那么

• 最终转移方程为

**注意:**为什么不能只找最近的进行判断？因为能否到达 受之前所有能到达位置的影响，而且最近的可到达位置，并不一定能到最终位置，例如 [3,0,0,5,0,0,1,0,1]

初始条件和边界情况

位置0为true

运算顺序

• 设 表示青蛙不能跳到石头

• 初始化 f[0]==true

• 计算 f[1],f[2]....,f[n-1]

• 返回结果为 f[n-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var canJump = function (nums) {
    var f = [true],
        n = nums.length;
    for (var j = 1; j < n; j++) {
        f[j] = false;
        for (var i = 0; i < j; i++) {
            if (f[i] && i + nums[i] >= j) {
                f[j] = true;
                break;
            }
        }
    }
    return f[n - 1];
};

复杂度分析

• 时间复杂度：,每次需要重复遍历已经遍历过的元素所以，

• 空间复杂度：