n = 10 +++ Flyover building costs 18 5 19 12 14 7 8 14 18 12 14 19 17 6 15 8 12 11 15 11 9 11 10 20 5 12 15 9 10 7 8 7 7 7 14 16 9 17 9 6 8 18 20 5 19 14 8 10 20 18 17 8 8 6 7 8 13 18 12 18 20 16 20 6 18 13 18 6 9 6 7 13 20 6 13 18 15 16 8 14 13 20 18 16 5 20 20 14 17 11 +++ Part 1: Greedy algorithm Building flyover from (0,1) to (1,1): Cost = 5 Building flyover from (1,3) to (2,3): Cost = 6 Building flyover from (2,4) to (3,4): Cost = 5 Building flyover from (3,4) to (4,4): Cost = 14 Building flyover from (4,6) to (5,6): Cost = 8 Building flyover from (5,6) to (6,6): Cost = 13 Building flyover from (6,7) to (7,7): Cost = 6 Building flyover from (7,8) to (8,8): Cost = 8 Building flyover from (8,9) to (9,9): Cost = 11 Total cost of the horizontal segments = 40 --- Total cost = 116 +++ Part 2: Dynamic programming algorithm --- Total cost = 78 +++ Part 3: Dynamic programming algorithm with solution Building flyover from (0,3) to (1,3): Cost = 12 Building flyover from (1,3) to (2,3): Cost = 6 Building flyover from (2,3) to (3,3): Cost = 20 Building flyover from (3,3) to (4,3): Cost = 7 Building flyover from (4,3) to (5,3): Cost = 5 Building flyover from (5,3) to (6,3): Cost = 6 Building flyover from (6,3) to (7,3): Cost = 6 Building flyover from (7,3) to (8,3): Cost = 6 Building flyover from (8,4) to (9,4): Cost = 5 Total cost of the horizontal segments = 5