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) & \mbox{if } j=1 \\ +\infty & \mbox{if } j>1 \end{cases}$$.

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

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

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

• How does it ensure that all cars have to be used? Mar 20 '20 at 20:19
• By definition of $OPT[n,3]$, the last car used must be $c_3$. Moreover, the first car used must necessarily be $c_1$ (since $OPT[1,j]$ is finite iff $j=1$). Finally, notice that if car $c_j$ is used to travel to the $i$-th city (with $i>1$), then the formulas ensure that car used to reach the $(i-1)$-th city is either $c_j$ or $c_{j-1}$ (if $j>1$). This means that a solution cannot use $c_1$ immediately before $c_3$, i.e., $c_2$ must be used as well. Mar 20 '20 at 22:17
• So you are imposing an order of cars to be 1, 2, 3 ? Mar 20 '20 at 22:53
• No, I am imposing that the order of cars is $c_1, c_2, c_3$, which is some permutation of $1,2,3$. Mar 20 '20 at 22:54
• for each permutation , you need to run the same equations right? I mean for .e.g. c1 = 1, c2= 2, c3 = 3 and then c1 = 1, c2 = 3, c3 = 2 then c1 = 2, c2 = 1, c3 = 3 etc. right? Mar 20 '20 at 22:56