Step 1 and step 2 are given above. I need only q4 to be done. Use any programming language.

4. There is a small real estate firm which in some months maintains an office in Coquille, OR (code C) and in others in Drain, OR (code D), and moves back and forth between these two cities (they can only afford to have one location operating at a time). This company wants to have the cheapest possible location plan - the two cities have different operating costs and these costs can change from month to month. We are given M, a fixed cost of moving between the two cities, and lists C = (ci, ..., Cn) and D = (d1,..., dn). Here c; is the cost of operating out of Coquille in month i, and di is the cost of being in Drain that month. Suppose that M = 10, C = (1,3, 20, 30), and D = (50, 20, 2, 4). If the location plan is (C, C, D, D), its cost will be 1+3 + 10 +2 +4 = 20. On the other hand, the cost of the plan (D, D, C, D) is 50+20+10+20+10+4 = 114. The goal here is to (start to devise a dynamic programming algorithm which, given M, C, and D, determines the cost of the optimal plan. The plan can start in either city, and end in either city. Note that you will likely need two subproblems, which will be mutually recursive. [8 points] step 1 describe the structure of the subproblem step 2 find a recurrence for the optimal value of the subproblem in terms of smaller subproblems Perform just these two steps for the two problems listed below. Do not write (pseudo) code - just the subproblem and recurrence structure. 3. You work for the OR state highway agency and must place warning signs along a certain road. Along the way there are n locations at which you may place a sign, at mile posts m;