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.
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..)
2 4 1 5 1 1 2
3 3 2 5 3 2 2
1 1 5 4 3 3 3
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.