Let us consider the simpler versions of these problems where edges are unweighted.
1. Given a graph $G$, check if $G$ has a cycle.
2. Given a graph $G$ and a number $k$, check if $G$ has a cycle of length at least $k$.
The first one is easy and can be solved using DFS. The second one is NP-hard.
Let's look at an even simpler problem:
1. Given a graph $G$ and two vertices $s$ and $t$, check if there is a simple path from $s$ to $t$ in $G$.
2. Given a graph $G$ and two vertices $s$ and $t$ and a number $k$, check if there is a simple path from $s$ to $t$ in $G$ of length at least $k$.
All of these problems are of the same flavor. The top one is easy while the bottom one is NP-hard. I will explain the difference for the last one because it is simpler but the same explanation applies to the other pairs.
The reason that the top ones are easy while the bottom ones are not is the result of the structure of the answers for these problems.
Let's first look at the problem of finding a simple path and try to solve it recursively. If we just try to solve this problem directly we would need to keep track of the vertices that we have used so far:
$SimplePath(s,t,G) :=$ there is a path from $s$ to $t$ in $G$.
$SimplePath(s,t,G)$ iff
$s=t$ or for some $u\in G$ $SimplePath(s,u,G-t)$ and $ut \in G$.
If we try to solve the problem with this naive recursive algorithm it will take exponential time: there exponentially many possibilities for the set of unused vertices! We have to be smarter.
Why did we get exponentially many possibilities? Because we were trying to find a simple path and to enforce this condition we needed to keep track of unused vertices.
OK, so let's drop that condition and see where we can get:
Consider the problem of a finding a path (not necessary simple) from $s$ to $t$. 433
Since the path doesn't need to be simple we don't need to keep track of unused vertices. In other words, the graph doesn't change over time.
$Path^G(s,t) :=$ there is a path from $s$ to $t$.
$Path^G(s,t)$ iff
$s=t$ or
for some $u\in G$ $Path^G(s,t)$ and $ut \in G$.
But we are not done yet. The issue is that we don't know if $Path^G(s,u)$ is a smaller problem than $Path^G(s,t)$. So this recursive solution might end in a loop and never terminate.
To avoid this we can add an extra parameter that makes sure the problem gets smaller: the number of edges in the path.
$Path^G(s,t,k) :=$ there is a path from $s$ to $t$ with at most $k$ edges.
$Path^G(s,t,k)$ iff
$k=0$ and $s=t$ or
$k>0$ and for some $u\in G$ $Path^G(s,u,k-1)$ and $ut \in G$.
Now note that there is a simple path from $s$ to $t$ iff there is a path from $s$ to $t$ with at most $n$ edges. In other words:
$SimplePath(s,t,G)$ iff $Path^G(s,t,n)$.
The essential points here are:
1. Every (nontrivial) simple path from $s$ to $t$ consists of a simple path from $s$ to some vertex $u$ and an edge $ut$.
2. We can assume that $t$ does not appear in the simple path from $s$ to $u$.
3. We don't need to explicitly keep the list of unused vertices.
These properties allow us to have a smart recursion for the existence of a simple path problem.
Now these do not apply to the problem of finding a path of length at least $k$. We don't know how to reduce the problem of finding a simple path of length at least $k$ to a smaller subproblem without keeping the list of unused vertices. 433