Question

Dynamic programming multisatge recurrence relation

Answer 1

To solve a problem by using dynamic programming. Find out the recurrence relations. Represent the problem by amultistage graph. Recursion is sometimes called “backward chaining”: start with the goal you want choosing your sub goals on an as-needed basis.

Answer 2

A multistage graph G=(V,E) is a directed graph in which the vertices are partitioned into k>=2 disjoint sets Vi, 1<=i<=k. ... A dynamic programming formulation for a k-stage graph problem is obtained by first noticing that every s to t path is the result of a sequence of k-2 decisions.