Dear all Can I know if dynamic programming can solve any optimization problem and if the obtained solution from DP is always optimal? If not, in what cases DP is not able to find the optimal solution? Thanks
asked
Amin-Sh |

In theory, dynamic programming can solve any optimization problem involving a finite number of discrete decisions variables, each of which has a finite domain. Assuming dynamic programming is done properly, and assuming it does not run out of time or memory, it is guaranteed to find an optimal solution. In practice, the number of stages and states can explode exponentially, so DP is not always practical.
answered
Paul Rubin ♦♦ |