A clarification regarding dynamic programming.

72 Views Asked by At

This is a question regarding dynamic programming.

The document to which I am referring is this (pg 325). It says that $$v_n(s_n)=\text{Min}\{t_n(s_n)+v_{n-1}(s_{n-1})\}$$

Here $v_n(s_n)$ is the minimum time spent on and after the $n^{th}$ stage.

Doesn't the "Min" function work for at least two values? How does $\text{Min}\{t_n(s_n)+v_{n-1}(s_{n-1})\}$ even make sense??

1

There are 1 best solutions below

0
On

I think they meant something like $$v_n(s_n)=\text{Min}_{i\leq n}\{t_i(s_i)+v_{i-1}(s_{i-1})\}$$, or the minimum over all the previous states + cost of next state

Take a look at this to check the possible dyn. prog. relations.