This problem is easily solved if you:
- transform the input graph $G=(V,E)$ by either creating $n-1$ "levels", where each level is a copy of $G$ and edges go from one level to the next; or
- consider the line graph $G'$ of $G$ instead (so that edges in $G$ become vertices in $G'$, and two vertices in $G'$ are adjacent if the corresponding edges in $G$ share an endpoint); or
- For each color $c \in \{red, blue\}$, identify the maximal components $C$ of $G$ such that connectivity within $C$ is preserved using only edges of color $c$.
If you insist in using a dynamic programming algorithm, then the problem can be solved in $O(m)$ time using a Dijkstra-like algorithm.
Let's start with some definitions:
Given a color $c \in \{red, blue\}$, define a $c$-ending path as a simple path $P$ such that either 1) $P$ is empty, or 2) $P$ ends with an edge of color $c$.
Given a path $P$, let $\ell(P)$ be the number of color changes encountered when traversing $P$.
We will say a path $P$ from $s$ to $v$ is a shortest $c$-ending path if there exist no other $c$-ending path $P'$ such that $\ell(P') < \ell(P)$.
We will call $\eta(v,c)$ the value of $\ell(P)$, where $P$ is a shortest $c$-ending path from $s$ to $v$.
According to the above definitions $\eta(s, red) = \eta(s, blue) = 0$.
Moreover, the following suboptimality property holds:
Claim: Let $P$ be any shortest $c$-ending path from $s$ to $v$, let $u \in P$.
The subpath $P[s:u]$ of $P$ going from $s$ to $u$ is a shortest $c'$-ending path where $c'$ is the color of the incoming edge in $u$ (if $u=s$ then $c'$ is any color).
Proof:
Assume that $u \neq v$, otherwise the claim is trivial.
Let $c''$ be the color of the edge leaving $u$ in $P$.
Suppose towards a contradiction that $P[s:u]$ is not a shortest $c'$-ending path.
Let $P'$ be a shortest $c'$-ending path from $s$ to $u$, and notice that $Q = P' \circ P[u:v]$ is a (not necessarily simple) path from $s$ to $v$.
$Q$ ends with an edge of color $c$ and we have:
$$
\ell(P) = \ell(P[s:u]) + 1_{c' \neq c''} + \ell(P[u:v])
> \ell(P') + 1_{c' \neq c''} + \ell(P[u:v])
= \ell(Q),
$$
contradicting the fact that $P$ is a shortest $c$-ending path. $\square$
For each node $v$ we will maintain two upper bound $\tilde{\eta}(v, red)$ and $\tilde{\eta}(v, blue)$ on $\eta(v, red)$ and $\eta(v, blue)$, respectively. Initially $\tilde{\eta}(s, red)=\tilde{\eta}(s, blue)=\eta(s, red) = \eta(s, blue) = 0$ while, for $v \neq s$, $\tilde{\eta}(s, red)=\tilde{\eta}(s, blue) = +\infty$.
Finally, we will maintain a priority queue $Q$ in which keys are pairs $(v,c)$ where $v$ is an unmarked vertex and $c$ is a color, and the corresponding priority will be $\tilde{\eta}(v, c)$. Initially all pairs $(v,c)$ are in the queue.
The algorithm proceeds as follows: while $Q$ is not empty, extract $(u,c)$ from $Q$; for each edge $e=(u,v) \in E$ let $c'$ be the color of $e$ and set $\tilde{\eta}(v, c) = \min\{\tilde{\eta}(v, c), \tilde{\eta}(u, c) + 1_{c \neq c'} \}$ (thus possibly updating the priority of $(v,c)$, if such a pair is in $Q$).
It is clear by construction that all values $\tilde{\eta}(v, c)$ are upper bounds to $\eta(v,c)$ as claimed. We now prove that, when the pair $(v,c)$ is extracted from $Q$, $\tilde{\eta}(v, c)$ is also a lower bound to $\eta(v,c)$, thus proving that $\tilde{\eta}(v, c) = \eta(v,c)$.
Claim: When $i$-th pair $(v_i,c_i)$ is extracted from $Q$, $\tilde{\eta}(v, c) \le \eta(v,c)$.
Proof:
Let $i$ be the smallest value such that, when $(v_i, c_i)$ is extracted from $Q$ we have $\tilde{\eta}(v_i, c_i) > \eta(v_i,c_i)$.
Since the values $\tilde{\eta}(v_i, c_i)$ never decrease during the execution of the algorithm and cannot become negative we know that $v_i \neq s$.
Let $P$ be a shortest $c_i$-ending path from $s$ to $v_i$ and consider the last vertex $x$ such that the incoming edge in $x$ in $P$ has color $c_x$ (if $x=s$ let $c_x$ be any color) and $x=v_j$ and $c_x=c_j$ for some $j<i$ (notice such a vertex always exists since the above conditions are satisfied for $x=s$).
Let $y$ be the vertex following $x$ in $P$ and $c_y$ be the color of the incoming edge.
Since $(v_i, c_i)$ was extracted instead of $(y, c_y)$ we must have:
$$
\tilde\eta(v_i, c_i) \le \tilde\eta(y, c_y)
$$
Moreover, since $(x, c_x)$ was already extracted from $q$ we have:
$$
\tilde\eta(y, c_y) \le \tilde\eta(x, c_x) + 1_{c_x \neq x_y} = \eta(x, c_x) + 1_{c_x \neq x_y}
$$
And, by suboptimality:
$$
\eta(x, c_x) + 1_{c_x \neq x_y} =
\eta(y, c_y) \le \eta(v_i,c_i),
$$
which is a contradiction $\square$.
The sought quantity is then $\min\{\tilde\eta(t,red), \tilde\eta(t,blue) \}$.
Finally, notice that the the priority can only decrease in $Q$, that the priority of the extracted pairs is monotonically increasing, and that the only possible values of the priorities are $\{0, 1, \dots, n\} \cup \{ +\infty \}$. Therefore it is possible to implement a priority $Q$ that requires $O(n+m) = O(m)$ time to perform all the required $O(n)$ insertions and $O(m)$ priority updates.
