Shortest path in DAG with path dependent arc costs I've got the following problem

Consider a DAG $G=(V,E)$ with $V=[v_1,…,v_n]$, and edge-set $E=[e_1,…,e_m]$, with associated costs $c_1,…,c_m$. The problem is to find the shortest paths from an initial vertex $s$ to multiple targets $t_1,…,t_k$, taking into account these costs. A typical shortest path problem.

However, my problem is slightly different:
the costs $c_1,…,c_m$ depend on the previously traversed nodes
Is there an alternative to the brute-force solution: find all the simple paths between $s$ and $t$ and then select the one with the lowest cost?

Path can be compared.
Take as example the following graph:
Red arcs are "checkpoint arcs". All the sub-paths having a red arc as last one can be compared, so a local decision can be taken. Similarly, costs are reset after traversing such arcs: 22->23 has a different cost if the subpath includes the arc 11->22 or not.



EDIT 2:

Costs are related to two sequences: $P$ and $Q$, where $len(P)=N$ and $len(Q)=M$. In the aforementioned case $M=N=4$.
Each element of $P$ and $Q$ is a tuple $(t,p)$. The tuple ($t_i,p_i)$ is the ith tuple of the sequence. Tuples are constrained on $t$: $t_{i+1} &gt; t_i$. There's no constraint on $p$.

Let $s_p$ a set of valid indices for the sequence $P$ and $s_qp$ a set of valid indices for the sequence $Q$. The cost $C(s_p,s_q)= C_t(s_p,s_q)+C_q(s_p,s_q)$ where $C_t = max(max(P[s_p][t]),max(Q[s_q][t])) - min(min(P[s_p][t]),min(Q[s_q][t]))$ and $C_p = max(max(P[s_p][p]),max(Q[s_q][p])) - min(min(P[s_p][p]),min(Q[s_q][p]))$

The cost $C(s_p,s_q)$ represents the "diameter" of the element obtained by merging the $s_p$th elements of $P$ and the $s_q$th elements of $Q$. 

Each path in the graph builds different $s_p$ and $s_q$ sets.
For example, the path 00,11,22,33 has a cost $C_{tot} = C(0,0)+ C(1,1)+ C(2,2)+ C(3,3)$, while the path 00 - 01 - 12 - 22 - 33 has a cost $C_{tot} = C(0,[0,1])+ C([1,2],2)+ C(3,3)$
Without further information on how the costs can vary, the problem is NP-complete. For instance, consider the following rule for setting costs:


If an edge would return to a previously-traversed node then its cost is $n$
If an edge reaches $t$ without previously traversing all other nodes then its cost is $n$
In all other cases the cost of an edge is $1$.


For such a rule, a Hamiltonian path has cost $n-1$ and all other paths have cost $n$ or greater. The problem could still be solved more efficiently than a brute-force search (e.g. in time $O(n^22^n)$ by dynamic programming) but not in polynomial time unless $\mathsf{P}=\mathsf{NP}$.

So if you want to find a polynomial time algorithm you will need to be much more specific about what sort of dependence between edge cost and previous path information is allowed.