educative.io

Educative

Better bottom-up solution (O(n) time complexity)

	const dp = new Array(jumps.length);
	let start = 0;
	let end = jumps[0];
	let steps = 1;
	while(start < jumps.length){
		let currentMax = 0;
		for(let i = start+1; i <= end && i < jumps.length; i++){
			currentMax = Math.max(currentMax, jumps[i]+i);
			dp[i] = steps;
		}
		steps++;
		start = end;
		end = currentMax;
	}
	return dp[jumps.length-1];
}

Right, The best solution for this problem should be O(n) instead of O(n^2).