Ho avuto un incarico sulla programmazione dinamica a causa della scorsa notte, ma ho dovuto renderlo incompleto perché non riuscivo a capire come risolvere l'ultimo problema:
The state wants to monitor traffic on a highway n miles long. It costs ci to install a monitoring device on mile i of the highway. The maximum distance between monitoring devices should not be more than d miles. That is, if there is a monitoring device on mile i, then there must be one monitoring device from mile i + 1 to mile i + d (or it is the case that i + d > n). The state wants a plan that will minimize the cost. Assume there is an array C[1..n] of costs.
Let vk be the cost of the best solution assuming a k mile highway and assuming a monitoring device on mile k. Given C and d, if the values of v1 through vk-1 are known, show how to determine the value of vk. You can write this mathematically, or provide pseudocode in the style of the book. Note you need to take into account all possible values of k from k = 1 to k = n.
Sono sicuro che un problema simile a questo verrà visualizzato durante l'esame e mi piacerebbe almeno sapere da dove cominciare a risolvere questo problema, quindi qualsiasi assistenza è apprezzata.