DP-LeetCode-55. 跳跃游戏

题目：

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

思路:

能跳到的位置一定是连续的一段，也就是不会出现可以跳到某个点j，但是不能跳到某个点之前的那个点j-1的这种情况。 反证法：假设现在可以跳到可以跳到某个点j，但是不能跳到某个点之前的那个点j-1。 那么这个可以跳到的点j一定是从之前的某个点i加上之前某个点i所能跳的步数nums[i]得到的。如果让这个点i加上之前这个点i所能跳的步数nums[i] - 1就可以跳到当前点j的前一个点j-1，所以跳到的位置一定是连续。

在这里插入图片描述

代码:

class Solution {
public:
    bool canJump(vector<int>& nums) {
    	// j表示最大可以跳多少步
        for (int i = 0, j = 0; i < nums.size(); i++) {
            if (j < i) {
                return false;
            }
            j = max(j, i + nums[i]);
        }
        return true;
    }
};