Leetcode_45. 跳躍遊戲 II

• 2020 年 5 月 11 日
• 筆記
• DP, 單調隊列, 題解

每個位置i有一個最大跳躍距離，求最小步數從0跳到n-1。

• dp[i]表示從0跳到i的最少步數，顯然可以轉移的狀態就是從i-a[i]到i-1。
• 因為是最小步數，考慮用優先隊列優化，再考慮到狀態有範圍的，所以用單調隊列，及時將失效的dp狀態移除。

code

class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        vector<int> q(n,0);
        vector<int> dp(n,0);
        int l=0,r=-1;
        dp[0]=0;
        q[++r]=0;
        for(int i=1;i<n;i++){
            while(l<=r && q[l]+nums[q[l]]<i){
                l++;
            }
            dp[i]=dp[q[l]]+1;
            while(l<=r && dp[q[l]]>dp[i]){
                r--;
            }
            q[++r]=i;
        }
        return dp[n-1];
    }
};