I came across the following problem :
There is an array of size n and you are currently located at the starting point of the array, you want to go to the ending point of the array by only using steps of +3 and -1.
like if you are at x you can either go to x+3 or x-1.
The total cost of this work will be equal to the sum of the values at the indices you go through to reach the end of the array. Find the minimum cost incurred.
ex.
[4 2 1 5 6]
here the best way is 4 -> 1 -> 2 -> 6
cost = 13.
size of array <= 1e3
1 <= a[i] <= 1e3
Approach :
There is a DP solution for this problem, but I was wondering can it be solved by dijkshtra algorithm where we assume that index x is connect to index x+3 and x-1, taking source as 0th index and target as (n-1)th index. The magnitude of edges being the value of the node it is leading to.
Auto comment: topic has been updated by vaibnak7 (previous revision, new revision, compare).
You just transposed this problem into standard dijkstra's algorithm problem, what makes you think it will not work?
Are you referring to:
dp[i] = min cost to get to index i? (And transition:dp[i] = a[i] + min(dp[i-3], dp[i+1]))If you tried this dp, iterating from i= 0 to n-1 wouldn't work as you don't have the property: previous dp states are calculated before the current dp state.
So what order to calculate dp states?
It turns out if we do a Dijkstra's, then the length array (in Dijkstra's) is exactly the above
dparray. And the order of nodes we visit in Dijkstra's does have the property: previous dp states are calculated before the current dp state.So the Dijkstra's and the dp solution are really the same solution, thought of differently