Given a directed Graph $G=(V,A)$ where $V$ is the set of vertices and $A$ is the set of arcs with corresponding positive costs $c_{i,j}$, find the cheapest path $p$ from a given vertex $s\in V$ to a given vertex $t \in V$ such that the path $p$ contains at most $H\in\mathbb{N}$ arcs.
Is this problem NP-hard? If yes, how does the reduction look like?
My thoughts so far:
If $|V|=n$, an upper bound for the number of paths originating at vertex s with length at most $H$ is $n^H$. Then we can check for each of those paths, if there is a subpath $p'\subseteq p$ such that $p'$ ends in vertex t and choose the one with minimum cost. Therefore, the whole procedure can be done in $\mathcal{O}(Hn^H)$.
It's definitely not NP-Hard. For each vertex $y$, let $N(y)$ be the set of vertices $u$ such that $uy$ is an arc in $G$. Then the cheapest path $C(y,k+1)$ from $s$ to $y$ with at most $k+1$ arcs satisfies
$$C(y,k+1)=\min_{u \in N(y)} [C(u,k)+c(uy)].$$
The length of the longest path is at most $n$. So if each vertex $y$ can keep track of $C(y,k)$ for $k=1,....,n$ then this leads to a polynomial-time algorithm.