LeetCode 55 Jump Game

概述

https://leetcode.com/problems/jump-game/

动态规划法

能否跳到终点处可以翻译为求能跳到的最大距离。

极值问题，直接动态规划。

略。

贪心法

反正没限制跳数，那我们能前往的最大距离，就是能前往的最大距离。

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