LC: 656. Coin Path - spiralgo/algorithms GitHub Wiki

656. Coin Path:

The Essence:

We have to react to the end of the array. It means, somehow we must pass over the indices with -1

The naive way of doing this would be trying to jump from the start to every possible index, and from there to every possible index, and so on. But in this case, it should be obvious that we will have to calculate the cost for each index more than once. Instead of this, we can apply dynamic programming here.

Details:

Please refer to the corresponding PR for a more detailed explanation and the DP implementation:

https://github.com/spiralgo/algorithms/pull/360