Jump Game

leetcode 55

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

子问题是, 看能不能跳到 i 位置,i 位置跳不到, 后面的必定更跳不到
由于初始站在索引 0 位置, 所以 0 位置是可以跳到的.dp[0] = nums[0]
dp[i] 表示子数组 [0,i] 内可跳的最远的位置
当索引到 k, 分两种情况:

1. k > dp[k - 1], 则此 k 索引位置不可达, 后面更不能到达, 退出返回 false
2. 更新 dp[k] 后, 若 dp[k] 已经包含最大索引, 则返回 true

JavaScript 代码如下：

var canJump = function (nums) {
    // if (nums.length === 1) {
    //     return true;
    // }
    let dp = Array(nums.length).fill(0);
    dp[0] += nums[0];
    let i = 1;
    for (; i < nums.length; i++) {
        if (i > dp[i - 1]) {
            console.log('此时 i 为', i);
            return false;
        }
        dp[i] = Math.max((i + nums[i]), dp[i - 1]);
        console.log(dp[i]);
        if (dp[i] >= nums.length - 1) {
            return true;
        }
    }
    // 只有一个元素的情况直接返回 true
    return true
};

Jump Game II

leetcode 45

给定一个非负整数数组 nums，初始时，你还是站在数组第一个元素位置。
元素的值表示在此元素位置可以跳的最大距离
你的目标是 ** 以最小的跳跃次数 ** 到达最后一个元素
你可以假设总能到达最后一个元素。

中文版的官方题解，解法一，贪心：

如果有多个位置通过跳跃都能够到达最后一个位置，那么我们应该如何进行选择呢？
贪心

1. 从最后一步向前查找, 找哪一个元素可以一步到达最后一个元素
2. 需要从左向右查找, 这样才能找到距离最后一个元素最远的位置,
3. 继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。

var jump1 = function (nums) {
    let position = nums.length - 1;
    let step = 0;
    while (position > 0) {
        for (let i = 0; i < position; i++) {
            if (i + nums[i] >= position) {
                position = i;
                step += 1;
                break;
            }
        }
    }
    return step;
};

时间复杂度：当数组全是 1 时，显然是 On
空间复杂度：O1

中文版的官方题解，解法二，贪心：

正向查找：

1. 索引 i 遍历数组
2. 使用一个变量跟踪当前索引 i 位置可以到达的最大的索引位置。
3. 当 i 索引到达此位置时，step 就加 1。

    let step = 0;
    let maxPos = 0;
    let end = 0;  // 边界, 索引到达边界时更新步数和边界
    for (let i = 0; i < nums.length - 1; i += 1) {
        maxPos = Math.max(maxPos, nums[i] + i);
        console.log('maxPos', maxPos);
        // 边界内有更远的跳跃距离? 那也得建立在这个元素在之前的跳跃距离内这个前提下
        // 所以, 需要步数加 1 和更新边界
        if (i === end) {
            end = maxPos;
            step += 1;
        }
        console.log(step, i);
    }
    console.log(step);
    return step;

不同路径 II-leetcode63

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动态规划解法：

var uniquePathsWithObstacles = function(obstacleGrid) {
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;
    let dp = Array.from(Array(m)).map(() => Array(n).fill(0));
    for(let i=0; i<m; i++) {
        // 有障碍物，则后面的不可达
        if (obstacleGrid[i][0] === 1) {
            break;
        }
        dp[i][0] = 1;
    }
    for(let i=0; i< n; i++) {
         // 有障碍物，则后面的不可达
        if (obstacleGrid[0][i] === 1) {
            break;
        }
        dp[0][i] = 1;
    }
    for(let i=1; i<m; i++) {
        for(let j=1; j< n; j++) {
            if (obstacleGrid[i][j] === 1) { // 有障碍物，则不可达
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }            
        }
    }
    return dp[m-1][n-1];
};

没啥好说的，就是 leetcode62 不同路径加了几个判断。