55. Jump Game

问题描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

题目链接：

---

思路分析

给一个数组，数组中的元素表示最多能向前走几步，稳从第一个元素开始，能否到达最后一个元素。

动态规划题目，设置一个长为n的dp数组，元素为false。然后dp[0] = true，从头开始遍历数组，如果数组元素对应的dp位是true，则将接下来的num[i]个元素也置为true。循环结束返回dp[n - 1]的值。

代码

class Solution { public: bool canJump(vector<int>& nums) { int n = nums.size(); if(n < 1) return false; vector<bool> dp(n, false); dp[0] = true; int num; for(int i = 0; i < n; i++){ num = nums[i]; if(dp[i]){ for(int j = 0; i + j < n && j <= num; j++){ dp[i + j] = true; } } } return dp[n - 1]; } };

时间复杂度： O(n) O ( n ) 空间复杂度： O(n) O ( n )

---

反思

比较简单的动态规划，思路明确之后就很容易解决。

评论区发现的常数空间复杂度的做法，计算最远能够循环到的位置是否等于n。在reach范围之内的都是可以走的，因为能走的位置肯定是连续的。

class Solution { public: bool canJump(vector<int>& nums) { int reach = 0, i = 0, n = nums.size(); for (; i < n && i <= reach; ++i) reach = max(i + nums[i], reach); return i == n; } };

时间复杂度： O(n) O ( n ) 空间复杂度： O(1) O ( 1 )