Prerequisites: Basic intuition or Dynamic programming
Problem in short:
There are N kingdoms numbered 1 to N. From i-th kingdom you can go up to (i + arr[i]) th kingdom. (You can choose any kingdom between i and (i + arr[i]) ) Mr Pompom starts from 1st kingdom and wants to reach N-th kingdom. Determine minimum number of kingdoms he will have to traverse to reach N-th kingdom.
Approach 1:Using basic intuition and observation (Range maximizing approach)
Ask yourself a question, where I would like to reach at any kingdom??Answer will turn out to be I want to go farthest kingdom possible as you want to reduce number of steps.
So at each kingdom’s tunnel, we select a tunnel within the coverage of present tunnel having maximum range, and continue doing the same till the range becomes equal or exceeds the position of last kingdom which is our destination. If there are more than one tunnels with same range then we select the farthest tunnel.
Now we can do some tricks while doing this like if the tunnel which is already taken into consideration in previous case and not chosen, then we won’t check for it another time as it won’t get selected anyway.(Why?)
Implementation (Source Code):
Approach 2:Using Dynamic programming
Use dynamic programming approach. Let dp[i] be the minimum number of kingdoms he will have to traverse to reach i-th kingdom. We can calculate dp[i] by (dp[Xi] + 1) , where Xi is minimum index from which we can reach i-th kingdom. The answer to the problem will be dp[n-1].
We will use dynamic programming to solve problem. Let dp[i]=minimum number of kingdoms needed to traverse to reach i-th kingdom.(Here 0-indexing is used)
So we will start looping from 0-th kingdom to N-1-th kingdom(0 -indexing) and keep assigning dp to all such remaining vertices that can be reached from that kingdom as dp[j]=dp[i]+1. We will break the Loop when no kingdoms are left. In each loop we will keep track of index from which kingdoms are remaining. Thus answer will be dp[n-1].
for(j=startingKindom;j<=(i+arr[i]) && j<n;j++)
Link to Solution(Code) using DP approach:
Time complexity analysis:
Both approaches have same time complexities of O(N). But as Dynamic Programming approach uses much memory it slightly takes more time than Range-Maximizing approach. Nevertheless both approaches are fast enough to pass out all the test cases.
NOTE:There is another possible acceptable solution which runs in O(nlog(n)) time complexity using bottom-up DP and segment tree.
Modification of question in which dp becomes much useful:
Suppose the position of firesafe bunker wasn’t fixed but changes in each query asked then in this case the answer would be directly dp[query]. Here, storing intermediate values by dynamic programming approach enables us to answer the query in O(1).
Suparshva Mehta & Aayush Kapadia