本文主要是介绍Leetcode 045 Jump Game II（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接：Leetcode 045 Jump Game II
解题思路：动态规划，dp[i]表示到第i个位置最少需要几步。用一个优先队列维护在第i个位置之前最小的dp[k]值，每次取出一个最小的k，判断k+num[k]是否大于等于i，如果大于等于，那么dp[i] = dp[k] + 1；否则删除k，并再取出优先队列的头，直到dp[i]被更新，然后将dp[i]也放入优先队列中。
class Solution {public:int jump(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;int* dp = new int[n];priority_queue<pair<int,int>> que;dp[0] = 0;que.push(make_pair(0, nums[0]));for (int i = 1; i < n; i++) {while (!que.empty() && que.top().second < i) que.pop();dp[i] = 1 - que.top().first;que.push(make_pair(-dp[i], i+nums[i]));}int ans = dp[n-1];delete dp;return ans;}
};
这篇关于Leetcode 045 Jump Game II（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
