I am talking about PROFTIP question.
What I thought of is there must be some state j to which we first go and then buy the fuel for the rest of the journey from the state j.
My dp[i][j] denotes the minimum cost of fuel needed to go from state i to state j.
So, my dp transition is dp[i][k] = dp[i][j] + fuel[j] * dist[j][k], where dist[i][j] is the minimum distance from state i to state j.
But, when I submitted this, it fails on some of the test cases.
So, then I tried dp[i][k] = dp[i][j] + dp[j][k] and it passed!
I didn’t understand whether I am going wrong OR the test cases are weak.
Can someone please help?