I was given a directed acyclic graph $G=(V,E)$ that has red and blue edges, and I want to generate a path from vertex $s$ to vertex $t$ such that the path has a maximum number of red edges.
After thinking about this I've decided to let every blue edge have a cost $0$ and every red edge to have a cost of $1$, which I think is the same problem.
I'm trying to use dynamic programming to generate this path but I'm confused on how to approach this to run this in linear time.
If the vertices are already in topological order (that is, all edges go from left to right) then you can start at $s$ and go in order. For each vertex, compute the maximum cost path from $s$ to that vertex, by considering all the edges that point into that vertex.
This takes $O(|V|+|E|)$ time.
If the vertices are not already sorted this way, then you should look at one of these algorithms for fixing that. These also take $O(|V|+|E|)$ time.
In general, this is nearly always the setup for dynamic programming in a directed acyclic graph, just because the topological sort is the primary way we can take advantage of the lack of cycles.