Design and Analysis of Algorithms

274 Design and Analysis of Algorithms

The principle can be applied in:

1. The forward direction, that is, x

i

, i = 0 to n, be the problem state variables; then take a decision about x

i

from x

i+1

, x

i+2

, . . . x

n

.

2. The backward direction, that is, x

i

, i = 0 to n, be the problem state variables; then take a decision about

x

i

from x

0

, x

1

, . . . x

i – 1

.

These are demonstrated in the following examples. Employing any of these strategies results in a

recursive approach to the problem solution. For example, in the case of the backward approach, the values of

x

1

, x

2

, . . . are computed successively.

Another important feature of dynamic programming is ...