We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Actually, it won't ever happen because of two reasons : First, tail is updated only if the value at head is smaller than the value at tail. Second, if we reach the head of snake again (without some other tail update), we can't get value smaller than the tail (Perhaps running through some example can help clarify it more). Thus, ensuring no tail of snake will be updated more than "number of other tails updates" (which is usually once), and hence, giving a linear solution.
In fact, I found DP very convenient and efficient for this particular problem. I gave this solution since you mentioned that you were stuck with DP because of snakes-case and were looking for some idea. Have a look if it helps you, else, its perfectly fine if you like some alternate approach :)
Snakes and Ladders: The Quickest Way Up
You are viewing a single comment's thread. Return to all comments →
Actually, it won't ever happen because of two reasons : First, tail is updated only if the value at head is smaller than the value at tail. Second, if we reach the head of snake again (without some other tail update), we can't get value smaller than the tail (Perhaps running through some example can help clarify it more). Thus, ensuring no tail of snake will be updated more than "number of other tails updates" (which is usually once), and hence, giving a linear solution.
In fact, I found DP very convenient and efficient for this particular problem. I gave this solution since you mentioned that you were stuck with DP because of snakes-case and were looking for some idea. Have a look if it helps you, else, its perfectly fine if you like some alternate approach :)