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. With this, it should be obvious that we might be calculating for each index more than once. Instead of this, we can apply dynamic programming here.
Instead of trying to jump forward, we can work backwards. The cost of jumping to last index from the last index itself is the value there. At the index before it, the cost would be the value there would be the value at this index + the target index. So, at every index, we consider all indices that we could jump to this index from, pick the minimum and add it to our paths data. To compare the costs, we store the costs in the input array to compare them when needed. So, the result by induction is that we eventually calculate the minimum cost for the 0-index, with the aid of which we also calculate the path.
Resolves: #243
Algorithm:
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. With this, it should be obvious that we might be calculating for each index more than once. Instead of this, we can apply dynamic programming here.
Instead of trying to jump forward, we can work backwards. The cost of jumping to last index from the last index itself is the value there. At the index before it, the cost would be the value there would be the value at this index + the target index. So, at every index, we consider all indices that we could jump to this index from, pick the minimum and add it to our paths data. To compare the costs, we store the costs in the input array to compare them when needed. So, the result by induction is that we eventually calculate the minimum cost for the 0-index, with the aid of which we also calculate the path.