Visiting Cities

There are a number of cities in a row, and there are two bus lines

that go between them. They both visit all cities in order, but one may

take longer than the other to go between any two cities.

Starting on or moving to the Blue line takes a certain amount of extra time.

There is no extra time required to start on or move to the Red line.

Determine the minimum cost to move from the first city to each of

the cities.

Example

red = [2, 3, 4]

blue = [3, 1, 1]

blueCost = 2

There are 4 cities numbered 0 through 3. Times from city 0 to cities

1, 2, and 3 are at indices 0, 1, and 2 respectively in the red and blue

arrays.

Through the explanation, an answer array, ans, will be created.

The minimum cost to go from city 0 to itself is 0. Now ans=[0]

• The time from city 0 to city 1 is 2 on the Red line and

3 + blueCost = 5 on the Blue line.

The blueCost applies when you start on the Blue line.

• The minimum time to city 1 is 2 on the Red line, so ans = [0, 2].

Continuing to city 2:

stay on the Red line, arriving at 2 + 3 = 5

switch to the Blue line and arrive at 2 + 1 + 2 = 5.

• The blueCost applies when you switch to the Blue line.

In this case, you arrive at time 5 regardless of the carrier on the

second leg. Now ans = [0, 2, 5].

To get to city 3:

• take the Red line, arriving at 5 + 4 =9

o stay on the Blue line arriving at 5 + 1 = 6.

• The blueCost does not apply if you stay on the Blue line or

move to the Red line.

The final ans array is [0, 2, 5, 6].

My Approach was more of a greedy one, that checks what is currently cheaper, to take red line or blue switch to the blue line, It did not pass all test cases.

I'm pretty sure it is Dynammic Programming, but I do not see it.