Problem 2 (20 points) You are responsible for moving a robotic arm in a manufacturing line containing n stations. Your goal is to program the robotic arm so that it moves from station 1 to station n in the best possible way. In particular, you are given n stations and a 2xn table as shown below for n = 6. i 1 2 3 4 5 6 Ci 15 5 67 29 16 1 2 3 1 2 1 93 The first row indicates the cost of performing the task in the i-th station. The second row indicates how many stations to the right you can skip once you are at station i. For example, if you are at station 2, you have to pay" 5 units visiting that station but then you can move at most 2 positions to the right, visiting either station 3 or station 4, whichever you think is better. The goal is to minimize the total cost of the visited stations, starting in station 1 and ending in station n. [5 points] Consider the greedy algorithm that starts at station 1 and works as follows: From the current station i move to the furthest station to the right as indicated by the value mi. Continue along the same way until you reach station n. Either prove this strategy correct or find a counterexample showing that it doesn't work. [15 points] Give a dynamic programming algorithm that finds the best schedule for the robotic arm. Define OPT[i] to be the optimal cost of moving the robotic arm starting at station i and ending in station n. 1. (5 pts) Give a recursive solution to the problem by defining the sub-problems appropriately, Show the base case(s) as well. 2. (5 pts) Justify the correctness and use it to describe your DP algorithm. 3. (5 pts) What is the time and space requirements needed by your algorithm