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?