# Find cheapest path from 1st city to the $n$th city

The title may be a bit misleading, but this is essentially a DP problem. The problem is that we have $n$ cities labeled from $1, ... n$ and we are trying to find the cheapest way to travel from 1 to $n$. There is a cost for travelling from $i$ to $j$, $i < j$, cost being $c_{ij}$ but I'm only allowed $k$ hops at most.

The $k$ constraint has me stumped. Intuitively, we recurse from $i$ to $n$ for each value of $n$. How would I solve this using at most $k$ hops? And what would the complexity be?

• I suggest you keep thinking. Try to solve special cases like $k=1,2,3$ first. – Yuval Filmus Apr 27 '16 at 18:04
• There's an algorithm for this. It's called Floyd-Warshall Algorithm. You may look for that if that helps. – Syed Ali Hamza Apr 27 '16 at 19:03