Very elegant C++ solution, O(N) time, O(N) space, using DP and pruning


  • 0
    P
     class Solution {
            public:   
            	int jump(vector<int>& nums) {
            		if(nums.empty())    return -1;
            		int N = nums.size(),lastFarthest=0;  	        
            		vector<int> dp(N,N+1);
            		dp[0]=0;
            		for(int i=0;i<N-1;i++){
            			int cover_length = nums[i];//cover range:i ~ i+cover_length;
            			if(i+cover_length <=lastFarthest)   continue;  //pruning
            			if(i+cover_length >=N-1)	
            				return 1+dp[i];          //pruning
            			for(int j=lastFarthest+1;j<=i+cover_length && j<N;j++){
            				dp[j] = 1+dp[i];
            			}
            			lastFarthest = i+cover_length;
            		}
            		return dp[N-1];
            	}       
            };
        //nums:[2,3,1,1,4,1,2,3,1,2,1 ,2 ,1 ,3]
        //dp:  [0,1,1,2,2,3,3,3,3,4,4 ,5, 6 ,6]

  • 0
    B

    I think the time complexity of your algorithm is O(n^2) rather than O(n), but the pruning strategy is very good!


  • 0
    P

    well, I think it is O(N) because of prunning, each element in dp vector only need one time's calculation.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.