跳跃游戏 II - C++力扣45题

题目链接：https://leetcode.com/problems/jump-game-ii/description/

解题思路

这题算是中等难度吧，就是一眼能看出来解决方法的程度，但是优化上还是得多费一点脑子，下面的代码也不是最优解。基本上是一眼能看出来用 DP 就能把这题解决，这里就是套了一个 DP 模板，但很明显 DP 不是最优解，可以考虑看看贪心算法。

完整代码：

class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> dp(nums.size(), INT_MAX);
        dp[0] = 0;
        for(int i = 0; i < nums.size(); i++) {
            for(int j = 1; j <= nums[i]; j++) {
                if(i + j >= nums.size()) break;
                dp[i + j] = min(dp[i + j], dp[i] + 1);
            }
        }
        return dp[nums.size() - 1];
    }
};