Leetcode 55.跳跃游戏

问题描述

 问题链接：Leetcode 55.跳跃游戏

1、贪心

• 思想：每一次都找到局部最优解
• 具体分析：
  • 拿数组 a = [2, 3, 1, 1, 4] 举例
  • 首先，我们必能跳到索引位置0，即 a[0] 的位置，而 a[0] 的最大跳跃长度为 2，则在 a[0] 处、我们可以走 1 步 or 2 步
  • 这时，如果我们可以通过 a[0] 位置直接走到最后一个位置，那么我们一定可以在 从 a[0] 往后的两步之内(包括两步) 走到最后一个位置
  • 换句话说，如果 a[0] 的最大跳跃长度 + a[0] 当前位置索引 >= 数组 a 的最大索引， 则我们一定可以到达数组最大索引处、也就是数组的最后一个位置
  • 更进一步的，如果 a[0] 的最大跳跃长度 + a[0] 当前位置索引 = 数组 a 的最大索引， 那么只有在 a[0] 处走了最大跳跃长度才能到达最后位置；而 如果 a[0] 的最大跳跃长度 + a[0] 当前位置索引 > 数组 a 的最大索引， 则说明在 a[0] 处只需要走最大跳跃长度之内的某个值就能到达最后位置
  • 也就是说，只要 a[0] 的最大跳跃长度 + a[0] 当前位置索引 >= 位置 x， 那么 x 及 x 以前的位置就都能到达
  • 这样，我们只需要维护一个 最远可到达位置，在每走一步时都更新它，就可以判断我们是否能够到达某个位置
  • 我们把每一步的最远可到达位置设为局部最优解，则有：最远可到达位置(局部最优解) = max(上一个位置的局部最优解，当前位置索引 i + 当前位置的最大跳跃长度 nums[i])
  • 这样，如果当前位置可达，并且当前位置的局部最优解已经包含最后位置，则最后位置可达，该问题有解
• 代码：

bool canJump(vector<int>& nums) { int len = nums.size(); // 数组长度 int far = 0; // 最远可到达位置(局部最优解)初始化 for(int i = 0; i < len; i++) { // 当前位置 i 在能走的最远可到达位置之内，说明当前位置可达 if(i <= far) { // 更新局部最优解            far = max(far, i + nums[i]); // 若局部最优解包含了最后位置，说明最后位置可达，直接返回 true if(far >= len - 1) return true; } } return false; } 

• 时间复杂度 O(n)、只需要访问 nums 数组一遍，共 n 个位置；空间复杂度 O(1)、不需要额外的空间开销
   

2、回溯

• 思想：和贪心不同，贪心是在每走一步时只看最远的结果、也就是当前的最优解，而回溯是在每走一步时都穷尽可能的结果
• 具体分析：
  • 拿数组 a = [2, 3, 1, 1, 4] 举例
  • 首先，我们必能跳到索引位置0，即 a[0] 的位置，而 a[0] 的最大跳跃长度为 2，则在 a[0] 处、我们穷尽所有可能的走法，如果某个走法能够到达最后位置，则问题有解
  • 如果遍历完数组并穷尽完所有走法依然不能到达最后位置，则问题无解
• 代码：

bool canJumpHelper(vector<int>& nums, int len, int index) { // 每一次能走的最远距离受制于数组长度 int tmp = min(index + nums[index], len - 1); // 因为上面将最远距离限制在数组长度以内，所以这里的判定条件为 等于 而非 大于 if(tmp == len - 1) return true; // 穷尽当前位置上所有走法 for(int i = index + 1; i <= tmp; i++) { // 如果其中一个走法能到达数组最后位置，则返回 true，退出 if(canJumpHelper(nums, len, i)) return true; } // 穷尽所有走法依然无解，则返回 false，退出 return false; } bool canJump(vector<int>& nums) { int len = nums.size(); // 数组长度 return canJumpHelper(nums, len, 0); // 从索引 0 开始回溯 } 

• 时间复杂度 O(n^n)、穷尽了 n 个位置上的所有走法；空间复杂度 O(n^n)、每一次回溯都有一个 tmp 记录最远距离(此项可优化)
   

3、动态规划

• 思想：通过已知解求未知解
• 具体分析：
  • 拿数组 a = [2, 3, 1, 1, 4] 举例
  • 首先，我们必能跳到索引位置0，即 a[0] 的位置，所以 a[0] 是我们在初始条件下唯一的已知解
  • 然后，由已知解 a[0] 为 benchmark，经 a[0] 处的最大跳跃长度 2 来查找未知解，即 从 a[0] 走一步到达的 a[1] 和 从 a[0] 处走两步到达的 a[2]，当然，当我们知道我们能够到达 a[1] 和 a[2] 处时，原本是未知解的 a[1] 和 a[2] 就变成了已知解
  • 这时，我们再基于已知解 a[1] 和 a[2] 继续去查找未知解，直到得到数组末尾 a[4] 的解的信息
  • 正向来看可能有些绕，不如反过来看，在我们不知道未知解 a[1] 的情况时，我们可以通过它的前一个已知解元素 a[0] 来判断它的情况， 即 已知解 a[0] 可达、且由 a[0] 走一步可达 a[1]，故 a[1] 可达
  • 那么在本问题上，我们最终求的是数组末尾元素是否可达，即 未知解 a[4] 的情况，而 a[4] 的情况可由它之前的 4 个元素 a[0] ~ a[3] 来得到
  • 例如，在 a[3] 处走一步即可达 a[4]，那么 问题转化为 只需 a[3] 可达即可； 而 a[3] 可由 a[2] 处走一步得到，那么 问题转化为 只需 a[2] 可达即可； 再看 a[2]，它可由 a[1] 处走一步得到，而 a[1] 可由 a[0] 走一步得到，a[0] 是我们的已知解、它必可达，那么 a[4] 可达
  • 值得注意的是，并非一定要由 a[ i ] 的前一个元素 a[ j ] 来推导，只要 j < i 时，由 a[ j ] 能到达 a[ i ] 都可
  • 现在，我们写出状态转移方程，1 表可到达、0 表不可到达：
    
    $a[i]=begin{cases} 1 & a[j] ==1 && j + nums[j] >=i, _{j<i}\ 0 & else\ end{cases}$

    a[i]={10​a[j]==1  &&  j+nums[j]>=i, j<i​else​

• 代码：

bool canJump(vector<int>& nums) { // 声明 dp 数组，用于存储当前位置是否可达 并 初始化第一个位置为可达     vector<bool> dp(len, false);     dp[0] = true; for(int i = 1; i < len; i++) { for(int j = i - 1; j >= 0; j--) { // 状态转移方程：如果 i 之前的某个位置 j 可达，并且从位置 j 可跳到当前位置，则当前位置可达 if(dp[j] == true && j + nums[j] >= i) {                 dp[i] = true; // 只要知道一个可达信息就行了，不需要得到 i 之前元素到 i 的全部可达信息 // 故在此处直接退出当前循环 break; } } } return dp[len - 1]; } 

• 时间复杂度 O(n^2)、n 个位置上各有 n 个子问题；空间复杂度 O(n)、需要一个 dp 数组来标记节点可达状态
   

4、总结

• 就本题来说，最容易想到的就是回溯的暴力解法，回溯是一个自顶向下的求解过程， 就数组 a = [2, 3, 1, 1, 4] 来说，已知解 a[0] 相当于树的根节点，未知解 a[4] 相当于树的叶节点，回溯的过程是一个从根节点向下发散找到某个特定的叶节点的过程
• 在回溯的基础上优化，每一步回溯只取当前最优解， 这就是贪心思想，当然了，当前最优解并不一定能使最终结果最优
• 动态规划是一个自底向上的求解过程， 每一步决策都依赖于当前状态，随即又引起状态转移，难点在于写出状态转移方程