LeetCode 45 Jump Game II

概述

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

动态规划法

dp[i] 表示从第 i 点出发，到达终点的最小跳数。

贪心法

每次在力所能及的选择中，选择一个跳的最远的（其本身位置 + 能跳多少格）。

四连 WA，看着简单。

注意，是 i < nums.size() - 1，因为 nums.size() - 1 就是终点。

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