LeetCode 45 Jump Game II

标签: 贪心法 LeetCode 发布于:2022-02-22 10:28:27 编辑于:2022-02-22 10:28:27 浏览量:872

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/