educative.io

Educative

Bottom-up solution - why do we compare dp[end] itself with dp[start]+1?

Why do we take the minimum value between the current jump-count and the jumps needed to reach the current index + 1?
in code, it’s dp[end] = Math.min(dp[end], dp[start]+1);

I understand the dp[end] = dp[start] + 1 when end=start+1; end <= start+jumps[start] .
But I don’t understand why do we compare dp[end] itself with dp[start]+1. According to dp[end] = dp[start] + 1, dp[end]> dp[start] + 1.

Did I miss anything?

@Franklin I think before the end there can be more starts that can reach that end (the end may iterate through more than one at a time), so we need to take the minimum between the two. I could see that we can check if (dp[end] == Integer.MAX_VALUE) then assign dp[end] equals to dp[start]+1; instead using Math.min, but the minimum checking way help us understand more about the problem that the current end can be reached by more than one start.