The following figure represents a graph of the possibile flights from one airport to another. Note that a flight should always originate from $0$ and terminate at $2$. Find the maximum possible number of flights you can take obeying the sequence $(cacbcbbbbaaacba)$ which represents the flight type. You may choose your route using only a subset of the elements of the sequence as well, but that has to have the same order as in the sequence like for example, cacbcbac is a valid sequence of flight types if that takes you from airport $0$ to $2$ (this is an example, it doesn't work) Also, you can originate and terminate at the same airport at you will (for joy rides).
I had been experimenting the possible routes and finally encountered that the number of rides can be maximised in this way - $0\to 0\to 0\to 4\to 2 \to 4 \to 1 \to 2 \to 4 \to 2$ which is $cccbbaaacb$- a valid subset of $cacbcbbbbaaacba$.
But how to know if this is correct? I did verify with the answer and it is indeed correct, but isn't there a solid way to do these kinds of problems instead of experimenting and considering several cases? Any nice idea would be appreciated.
Begin by writing down adjacency matrices $A, B, C$ for each of the flight types: for example, $$ A = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{bmatrix}. $$ Multiplying together $CACBCBBBBAAACBA$ would give us a matrix whose $(i,j)$ entry records the number of paths from $i$ to $j$ exactly following the sequence "cacbcbbbbaaacba". There might well not be any such paths, of course.
Multiplying together $$(I+C)(I+A)(I+C)(I+B)(I+C)(I+B)(I+B)(I+B)\\(I+B)(I+A)(I+A)(I+A)(I+C)(I+B)(I+A)$$ makes using a letter optional: you can choose the $I$ term from a factor to stay put, or the other factor to take a step. This will give us a matrix whose $(i,j)$ entry records the number of paths from $i$ to $j$ following a subsequence of "cacbcbbbbaaacba".
However, this doesn't distinguish between the terms we pick, so it doesn't record the number of flights taken. To figure out how long these paths are, instead multiply together $$(I+xC)(I+xA)(I+xC)(I+xB)(I+xC)(I+xB)(I+xB)(I+xB)\\(I+xB)(I+xA)(I+xA)(I+xA)(I+xC)(I+xB)(I+xA).$$ Here, every time we actually take a flight, we pick up a factor of $x$. This gives us a matrix whose $(i,j)$ entry is a generating function for paths from $i$ to $j$; its $x^k$ factor will give us the number of paths of length $k$.
Doing this gets me $$18 x^{10}+74 x^9+222 x^8+498 x^7+612 x^6+411 x^5+201 x^4+85 x^3+15 x^2$$ which suggests that there are $18$ solutions which take $10$ flights, and that's the longest possible.
(Okay, fine, we could have done the same thing without adjacency matrices at all, using dynamic programming or some such.)