地址

https://leetcode.com/problems/jump-game-ii/description/

题目

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.

思路

dp[i]:表示跳到i位置最少需要多少步。最简单的转移方程自然是$dp[k]=min(dp[k],dp[i]+1),k<=i+a[i]$，可惜这会TLE，这是$O(n^2)$的，需要优化。
下面举例说明优化方法（dp初始化为[0,inf,inf,inf,inf]）：
  1. a[1]=2 ==> dp[3]=min(dp[3],dp[1]+1=1) ==> dp数组[0,inf,1,inf,inf]
  2. a[2]=3 dp[2]=min(dp[2~5])=dp[3]=1 ==> dp[5]=min(dp[5],dp[2]+1) ==> dp数组[0,1,1,inf,2]
  3. a[3]=1 dp[3]=min(dp[3~5])=1 ==> dp[4]=min(dp[4],dp[3]+1) ==> dp数组[0,1,1,2,2]

  4. a[4]=1 dp[4]=min(dp[4~5])=2 ==> dp[5]=min(dp[5],dp[4]+1) ==> dp数组[0,1,1,2,2]

    从上面的例子可以看出每次只需要更新$dp[i+a[i]]=min(dp[i+a[i]],dp[i]+1)$,对于$dp[i+k],0<k<a[i]$可以隐式得到，所以在每次开头通过$dp[i]=min(dp[i~size(a)])$可以更新正确的dp[i]值。
    区间最小值用线段树和树状数组处理即可。

代码

class Solution {
public:
    int n,mi[100007];
    void add(int x,int v)
    {
        while(x<=n) mi[x]=min(mi[x],v),x+=x&-x;
    }
    int get_mi(int x)
    {
        int ret=0x3f3f3f3f;
        while(x) ret=min(mi[x],ret),x-=x&-x;
        return ret;
    }
    int jump(vector<int>& nums) {
        int dp[100007],ans=0x3f3f3f3f;
        memset(mi,0x3f3f3f3f,sizeof mi);
        memset(dp,0x3f3f3f3f,sizeof dp);
        dp[0]=0,n=nums.size();
        for(int i=0;i<n;i++)
        {
            dp[i]=min(dp[i],get_mi(n-i));
            if(i+nums[i]<n&&dp[i+nums[i]]>dp[i]+1)
            {
                dp[i+nums[i]]=min(dp[i+nums[i]],dp[i]+1),add(n-i-nums[i],dp[i]+1);
            }
            else if(i+nums[i]>=n)
                add(1,dp[i]+1);
        }
        return dp[n-1];
    }
};