Assembly Line Scheduling - Data structures

I am trying hard to understand how the table is computed in this 'Assembly line scheduling' problem in Chapter 15 'Dynamic Programming' on Intorduc开发者_C百科tion to Algorithms book by Cormen.

Can anyone give me a hint on what are the two tables about & how they get calculated ? Been searching on google for past 2 hours.

---

The 1st table contains the fastest way to pass station Si,j:

• f1[j] is the fastest way to pass station j of assembly line 1
• f2[j] is the fastest way to pass station j of assembly line 2

For example, f2(3)=22, since 2+7+2+5+6=22, and this is the fastest way to pass station 3 of assembly line 2.

In the 2nd table, li(j) shows the assembly line number (1 or 2) that is used in step j-1 as part of the fastest way to reach li(j).

For example, l1(2)=1 since the fastest way to reach station 2 in assembly line 1 is through station 1 on assembly line 1. (2+7 < 4+8+2)

l2(2)=1 since the fastest way to reach station 2 in assembly line 2 is through station 1 on assembly line 1. (2+7+2 < 4+8).

---

f(2) = 22 because it is the shortest way (time) to pass station 2,3 :)
You have to look all ways and find shortest f(1)j is station 1,j
I know because I took this lesson too :)

---

Sorry for digging up a 4-year-old question, but it's the first result on google.

The answer provided by Lior is incorrect. f1(j) is NOT for passing stations starting at assembly line 1. If so, why is f1(2) = 18? when the optimal path is 2+7+2+5= 16.

Also, for f2(3) = 22, 4+8+5+1+3 does NOT equal 22. It's 21.

fi(j) is actually the function of the fastest way to get to jth station on ith line (as answered by Kubra). f2(3) = 22 because 2+7+2+5+6. That's the most efficient route to get to that specific station.

I hope my answer will save people's time, as i spent an hour on double-, triple-checking if i made a mistake understanding the problem and answers.

Thanks.