复旦大学：《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 08 Dynamic programming

Computing the fastest times Station Station Station StationStation Station S Assembly line 1 4 p Chassis Completed auto exits Assembly line2(8(5(6 4 Station Station Station Station Station Station j123456 23456 fU9182024 11012 12162225 l]1|2

Computing the fastest times 7 9 3 4 3 2 2 4 8 4 8 5 6 4 5 7 2 2 3 1 1 2 3 2 4 1 Chassis enters Assembly line 1 Completed auto exits Assembly line 2 Station S1,1 Station S1,2 Station S1,3 Station S1,4 Station S1,5 Station S1,6 Station S2,1 Station S2,2 Station S2,3 Station S2,4 Station S2,5 Station S2,6 9 18 20 24 12345 6 12 16 22 25 1 2 1 2345 6 1 2 1 f1[j] j f2[j] l1[j] j l2[j]

Computing the fastest times Station Station Station StationStation Station S Assembly line 1 4 p Chassis Completed auto exits Assembly line 2(8(5(64 Station Station Station Station Station Station j123456 23456 fU918202432|35 f=38 11012 2 121622253037 l]1|2

Computing the fastest times 7 9 3 4 3 2 2 4 8 4 8 5 6 4 5 7 2 2 3 1 1 2 3 2 4 1 Chassis enters Assembly line 1 Completed auto exits Assembly line 2 Station S1,1 Station S1,2 Station S1,3 Station S1,4 Station S1,5 Station S1,6 Station S2,1 Station S2,2 Station S2,3 Station S2,4 Station S2,5 Station S2,6 9 18 20 24 32 12345 35 6 12 16 22 25 30 37 1 2 1 1 2345 2 6 1 2 1 2 2 f1[j] j f2[j] l1[j] j l2[j] f * = 38 l * = 1

Constructing the fastest way Station Station Station StationStation Station S Assembly line 1 4 p Chassis Completed auto exits Assembly line 2(8(5(64 Station Station Station Station Station Station j123456 23456 fU918202432|35 f=38 11012 2 121622253037 l]1|2

Constructing the fastest way 7 9 3 4 2 2 4 8 8 5 6 4 5 7 2 2 3 1 1 2 3 2 4 1 Chassis enters Assembly line 1 Completed auto exits Assembly line 2 Station S1,1 Station S1,2 Station S1,3 Station S1,4 Station S1,5 Station S1,6 Station S2,1 Station S2,2 Station S2,3 Station S2,4 Station S2,5 Station S2,6 9 18 20 24 32 12345 35 6 12 16 22 25 30 37 1 2 1 1 2345 2 6 1 2 1 2 2 f1[j] j f2[j] l1[j] j l2[j] f * = 38 l * = 1 4 3

Constructing the fastest way Station Station Station StationStation Station S Assembly line 1 4 Chassis Completed auto exits Assembly line 2(8(5(64 Station Station Station Station Station Station j123456 23456 fU918202432|35 f=38 11012 2 121622253037 l]1|2

Constructing the fastest way 9 4 4 2 8 8 6 7 2 3 2 3 2 4 Chassis enters Assembly line 1 Completed auto exits Assembly line 2 Station S1,1 Station S1,2 Station S1,3 Station S1,4 Station S1,5 Station S1,6 Station S2,1 Station S2,2 Station S2,3 Station S2,4 Station S2,5 Station S2,6 9 18 20 24 32 12345 35 6 12 16 22 25 30 37 1 2 1 1 2345 2 6 1 2 1 2 2 f1[j] j f2[j] l1[j] j l2[j] f * = 38 l * = 1 3 4 1 4 5 1 3 1 5 7 2 2

Constructing the fastest way Station Station Station StationStation Station S Assembly line 1 4 Chassis Completed auto exits Assembly line 2(8(5(64 Station Station Station Station Station Station j123456 23456 fU918202432|35 f=38 11012 2 121622253037 l]1|2

Constructing the fastest way 9 4 4 2 8 8 6 7 2 3 2 3 2 4 Chassis enters Assembly line 1 Completed auto exits Assembly line 2 Station S1,1 Station S1,2 Station S1,3 Station S1,4 Station S1,5 Station S1,6 Station S2,1 Station S2,2 Station S2,3 Station S2,4 Station S2,5 Station S2,6 9 18 20 24 32 12345 35 6 12 16 22 25 30 37 1 2 1 1 2345 2 6 1 2 1 2 2 f1[j] j f2[j] l1[j] j l2[j] f * = 38 l * = 1 3 4 1 4 5 1 3 1 5 7 2 2