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?
Find cheapest path from 1st city to the $n$th city
algorithms;dynamic programming