Easy Java Code Soln., optimised O(N2) [DP+GREEDY]


#1

public class Solution
{
public int jump(int[] arr)
{
int n=arr.length, dp[]=new int[n], maxsteps=0;
// dp[i] => minimus steps to reach index i
Arrays.fill(dp,Integer.MAX_VALUE-1);
dp[0]=0;
for(int i=0;i<n;i++)
{
//optimisation, we only need to check(update) for indexes where we haven’t reached yet(greedy)

        if(i+arr[i]>maxsteps)
        for(int j=i+1;j<=Math.min((i+arr[i]),n-1);j++)
        {
            dp[j]=Math.min(dp[j],1+dp[i]);
            maxsteps=j;
        }
    }
    if(dp[n-1]==Integer.MAX_VALUE-1)
        return -1;
    return dp[n-1];
}

}