jump
jump

题目

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

1
2
3
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

1
2
3
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

题目分析

这是一个动态规划问题，通常，解决并完全理解动态规划问题需要以下 4 步：

  1. 从递归回溯解决方案开始
  2. 通过使用带有记忆属性的表进行优化(自上而下的[2]动态规划)
  3. 移除递归(自下而上的动态规划)
  4. 应用最后的技巧来降低时间/内存的复杂性

以下所有方法都可适用，只是时间复杂度和空间复杂度不同。

解题方法

回溯法

这是一个低效的解决方案，我们尝试从第一个位置到最后一个位置的每一个跳跃模式。我们从第一个位置开始，跳到每个可以到达的索引。我们重复这个过程，直到达到最后一个索引。卡住时，后退。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean canJumpFromPosition(int position, int[] nums) {
        if (position == nums.length - 1) {
            return true;
        }

        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                return true;
            }
        }

        return false;
    }

    public boolean canJump(int[] nums) {
        return canJumpFromPosition(0, nums);
    }
}

对于上面的代码，我们可以做的一个快速优化是从右向左检查nextPosition。理论上最坏的情况性能是一样的，但是实际上，对于愚蠢的例子，代码可能运行得更快。直观上来讲，这意味着我们总是试图跳得最大，以便尽快到达终点

所需的更改是:

1
2
3
4
// Old
for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++)
// New
for (int nextPosition = furthestJump; nextPosition > position; nextPosition--)

假定，在下面这个例子中，如果我们从 index 0开始，跳得越远越好，达到1，跳得越远越好，达到6。通过这样做，我们分三步确定0是一个好的索引。

Index 0 1 2 3 4 5 6
nums 1 5 2 1 0 2 0

为了说明这种优化不起作用的最坏情况，以下面的例子为例。无法从任何位置到达索引6，但将尝试所有组合。

Index 0 1 2 3 4 5 6
nums 5 4 3 2 1 0 0

上面这个例子回溯的前几步是: 0 -> 4 -> 5 -> 4 -> 0 -> 3 -> 5 -> 3 -> 4 -> 5 -> etc.

复杂度分析

  • Time complexity : $O(2^n)$. 从初始位置走到最后位置，有 $2^n$(upper bound) 种方法, $n$ 是数组 nums 的长度.
  • Space complexity : $O(n)$. 递归需要额外的空间分配给栈.

自上至下的动态规划

自上而下的动态规划可以被认为是优化的回溯。它依赖于这样的观察，即一旦我们确定某个指数是好的/坏的，这个结果永远不会改变。这意味着我们可以存储结果，而不需要每次都重新计算。

因此，对于数组中的每个位置，我们都记得 index 是好是坏。让我们调用这个数组 memo ，并让它的值为:好、坏、未知之一。这种技术被称为记忆化。

输入数组 nums = [2，4，2，1，0，2，0] 的记忆表示例如下图所示。我们用 G 代表好位置，用 B 代表坏位置。我们可以看到，我们不能从索引2、3或4开始，最终到达最后一个索引(6)，但我们可以从索引0、1、5和(一般)6开始。

Index 0 1 2 3 4 5 6
nums 2 4 2 1 0 2 0
memo G G B B B G G

Steps

  1. 最初，记忆表中所有元素是 UNKNOWN, 除了最后一个, (一般情况下) 是 GOOD (他一定能到达自己)

  2. 修改回溯算法，以便递归步骤首先检查索引是否已知(好/坏)

    1. 如果已知（KNOWN） 则返回 True / False
    2. 否则像以前一样执行回溯步骤

  3. 一旦我们确定了当前索引的值，我们就将其存储在 memo 表中

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
enum Index {
    GOOD, BAD, UNKNOWN
}

public class Solution {
    Index[] memo;

    public boolean canJumpFromPosition(int position, int[] nums) {
        if (memo[position] != Index.UNKNOWN) {
            return memo[position] == Index.GOOD ? true : false;
        }

        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                memo[position] = Index.GOOD;
                return true;
            }
        }

        memo[position] = Index.BAD;
        return false;
    }

    public boolean canJump(int[] nums) {
        memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;
        return canJumpFromPosition(0, nums);
    }
}

复杂度分析

  • 时间复杂度 : $O(n^2)$. 对于数组中的每一个元素 ， 比如 i ， 我们将会从他的右面查找下一个 nums[i] 元素 ，以找到 GOOD 索引 ， nums[i]最大可能是 $n$ ，$n$ 是数组长度。
  • 空间复杂度 : $O(2n) = O(n)$. 第一个 $n$ 来自于递归 ， 第二个 $n$ 来自于 memo 表的存储。

自下至上的动态规划

自上而下到自下而上的转换是通过消除递归来完成的。实际上，这实现了更好的性能，因为我们不再有方法堆栈开销，甚至可能从一些缓存中受益。更重要的是，这一步为未来的优化开辟了可能性。递归通常是通过尝试颠倒自顶向下方法的步骤顺序来消除的。

这里要做的观察是，我们只跳到右边。这意味着，如果我们从数组的右边开始，每次我们查询右边的位置时，该位置已经被确定为 GOOD 或 BAD. 这意味着我们不需要再重复了，因为我们总是会碰撞 memo 表.

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
enum Index {
    GOOD, BAD, UNKNOWN
}

public class Solution {
    public boolean canJump(int[] nums) {
        Index[] memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;

        for (int i = nums.length - 2; i >= 0; i--) {
            int furthestJump = Math.min(i + nums[i], nums.length - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (memo[j] == Index.GOOD) {
                    memo[i] = Index.GOOD;
                    break;
                }
            }
        }

        return memo[0] == Index.GOOD;
    }
}

贪心算法

一旦我们的代码处于自下而上的状态，我们就可以进行最后一次重要的观察。从一个给定的位置，当我们试图看是否能跳到一个 GOOD 位置时，我们只使用一个——第一个(见 break 语句)。换句话说，最左边的一个。如果我们把这个最左边的 GOOD 位置作为一个单独的变量来跟踪，我们可以避免在数组中搜索它。不仅如此，我们还可以完全停止使用数组。

从右向左迭代，对于每个位置，我们检查是否有潜在的跳跃达到 GOOD 的 index (currPosition + nums[currPosition] >= leftmostGoodIndex )。如果我们能达到一个好的指数，那么我们的位置本身就是好的。此外，这个新的好位置将是新的最左边的好索引。迭代一直持续到数组的开始。如果第一个位置是好指数，那么我们可以从第一个位置到达最后一个指数。

为了说明这个场景，我们将使用下图，对于输入数组 nums = [9，4，2，1，0，2，0] 。我们写 G 代表好，B 代表坏，U 代表未知。假设我们一直迭代到位置 0，我们需要决定索引0是否是好的。因为指数1被确定为 GOOD ，所以跳到那里就足够了，然后确保我们最终能达到指数6。大到足以一路跳到最后一个指数并不重要。我们只需要一种方法。

Index 0 1 2 3 4 5 6
nums 9 4 2 1 0 2 0
memo U G B B B G G

代码：

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

动态规划问题总结

动态规划问题常用步骤

通常，解决并完全理解动态规划问题需要以下 4 步：

  1. 从递归回溯解决方案开始
  2. 通过使用带有记忆属性的表进行优化(自上而下的[2]动态规划)
  3. 移除递归(自下而上的动态规划)
  4. 应用最后的技巧来降低时间/内存的复杂性

动态规划特点

动态规划仍带有一些递归特性，也可以改成回溯的形式，但是和较为傻瓜，一条路走到黑的回溯相比，动态规划有着自己的最优解决策：

它利用一张带有记忆属性的表来存储最优情况。

动态规划适用问题

能采用动态规划求解的问题的一般要具有3个性质：

  1. 最优化原理：假设问题的最优解所包括的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

  2. 无后效性：即某阶段状态一旦确定。就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响曾经的状态。仅仅与当前状态有关；

  3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到（该性质并非动态规划适用的必要条件，可是假设没有这条性质。动态规划算法同其它算法相比就不具备优势）。

更多动态规划问题

更多动态规划问题关注标签：动态规划