I am confused about how to go about dynamic programming questions, what are the steps to solving them, and how do I determine a recurrence relationship within these problems? It'd make sense that if the overall cost is the equation specified above then would the recurrence relationship then be that the WS(item) is equivalent to the WS(i-j) + j before it? Or like WS(i) = WS(i-j) + WS(j)? Can you help explain the process and thinking?

4. The Oregon Department of Transportation (ODOT) has decided to place a series of warning signs along a section of a major road. This is a one-way road and the dangerous sections are at mileposts (mi, m2, ..., mn). They wish to cover each of these locations, meaning that for each milepost there should be a sign at that point or at most k miles before it. Formally, for each milepost mi, it is covered if there is a sign at some mj GSi) with mi - m; sk. Signs can only be placed at a milepost and there is a cost c; to place a sign at mi. The input consists of [mi, m2, ..., mn], [C1,C2, ..., Cn), and k. You can assume that the mi are sorted (mi-1 0. The goal here is to determine the minimum total cost of a placement of signs at mileposts that covers all locations. To start a dynamic programming solution, we define subproblem WS(i) to be the minimum placement cost of warning signs such that (i) there is a sign at location mi and (ii) loca- tions mi, m2, ...,Mi-1 are also covered. The overall cost that we can report to ODOT is min{ WS(i) 1