Dynamic programming problem our uni is closed because of the COVID-19 and I'm trying to homelearn dynamic programming. 

In our algorithms book, there is the following problem: (an example problem for dynamic programming)


  A driver has 3 cars. He wants to use all of the 3 cars, but want to
  use the least gas. Each car has a different engine, so it will consume
  different amounts of gas to get to each destination. What is the least amount of gas
  we can consume while still using each car? After he switches cars, he
  can't go back to the previous car. 
  
  Input description:
  
  First is a number $n$, which is the number of destinations that he
  wants to reach.  Then there are 3 lines, each is the gas consumed
  while trying to reach each destination (line 1 is car 1, line 2 is car
  2, etc..)
  
  Example input:
  
  7
  
  2 4 1 5 1 1 2
  
  3 3 2 5 3 2 2
  
  1 1 5 4 3 3 3
  
  Example output:
  
  12 (third car (2 destinations), first car (4 destinations), second car (1 destination).)


However, I can't figure out how to start, as I'm still learning DP. Could you please help me or give me any hints?

I think it's a great good example problem, because other problems are very similar so if I master this one, I should be able to solve other problems.

Thanks!
Let $g(i,j)$ be the gas consumed when travelling to destination $i$ with car $j$.

Guess the optimal order $\langle c_1, c_2, c_3 \rangle$ of cars (there are only $3! = 6$ possible permutations). 

Define $OPT[i,j]$ as the minimum amount of gas needed for reaching the first $i$ destinations using cars $c_1, \dots, c_j$ in this order, with the constraint that each car must be used at least once. If no feasible solution exists then $OPT[i,j] = + \infty$.

According to the above definition, you have $$OPT[1,j] = \begin{cases}
g(1, c_1) &amp; \mbox{if } j=1 \\
+\infty &amp; \mbox{if } j&gt;1
\end{cases}$$.

and, for $i=2, \dots, n$: 

$$OPT[i,j] = g(i,c_j)+
\begin{cases}
OPT[i-1, j] &amp; \mbox{if } j=1 \\
\min\{ OPT[i-1, j], OPT[i-1, j-1] \} &amp; \mbox{if } j&gt;1
\end{cases}.$$

The solution to your problem is $OPT[n,3]$, which can be computed in $O(n)$ time using dynamic programming.