leetcode 45. 跳跃游戏 II(dp + 贪心)

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例1：

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例2：

输入: nums = [2,3,0,1,4]
输出: 2

🧡 算法分析

此题方法是用dp + 贪心

1. 设状态f(i) 表示到达i 所需要的最少步数
2. 通过枚举单纯的动态规划，我们可以知道，f[N] 的数组时单调递增的，大概是0，1，1，2，2，2…
3. 状态转移方程为f[i] = f[j] + 1, j 是 上一次到第一次到达i的位置
4. 输出状态置为 f(0) = 0， 需要定义辅助指针 j 记录，上一次到达 i 时，上一步的位置， j 从0 开始
5. 所以我们只用找到第一个能跳到i的点j，然后用j去更新i的状态即f[i] = f[j] + 1
6. 后面更新更多的点同理，只用找到能跳到的第一个点即可
7. 返回f(n - 1) 就是求的答案

💚 代码实现

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);

        for(int i = 1, j = 0; i < n; i ++)
        {
            while(j + nums[j] < i) j ++;  //找到能跳到i的第一个点
            f[i] = f[j] + 1;  // 直接更新f[i]
        }

        return f[n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

执行结果：

💙 时间复杂度分析

数组的每个元素最多被遍历两次，故时间复杂度为 O(n)。

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！