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.
Really interesting problem for practicing Dynamic Programming as well as Shortest Path in graphs.
I solved this problem and then looked up the editorial, where they've used a similar approach, except they store the value for all the k iterations of the flips.
You only need to store the values for the current and the previous iteration at any given time. Only exception is for the destination point *, where you just keep storing the min against the previous flip value.
Also the wording in the editorial could be improved, it is not so well explained, how we arrive at the intended solution. I've added comments in my solution if anyone is interested.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Coin on the Table
You are viewing a single comment's thread. Return to all comments →
Really interesting problem for practicing
Dynamic Programming
as well asShortest Path
in graphs.I solved this problem and then looked up the editorial, where they've used a similar approach, except they store the value for all the k iterations of the
flips
.You only need to store the values for the current and the previous iteration at any given time. Only exception is for the destination point
*
, where you just keep storing the min against the previousflip
value.This solution can be found here
Also the wording in the editorial could be improved, it is not so well explained, how we arrive at the intended solution. I've added comments in my solution if anyone is interested.