题目连接：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;
}
};
