<p>This is not a research level question. In any case DP is obtained by memoizing a recursion. If you start with an instance <span class="math-container">$I$</span> then the recursion generates several subproblems. You can obtain a dependency graph <span class="math-container">$G$</span> on these subproblems where each node is a subproblem and there is an arc <span class="math-container">$(I_i,I_j)$</span> if <span class="math-container">$I_j$</span> calls <span class="math-container">$I_i$</span>. This dependency graph must necessarily be a directed acyclic graph (DAG) if the original recursion is correct. Now to evaluate the subproblems and eventually find the answer for <span class="math-container">$I$</span>, one can use <em>any</em> topological ordering of <span class="math-container">$G$</span>. In general there can be many topological orderings. </p>

CC BY-SA 4.0
2018-10-25T12:32:46.480Z
2018-10-25T12:32:46.480Z
Chandra Chekuri
<p>1) Can every dynamic programming question be solved using 3 different orderings or can there be more than 3 or less than 3 ( like unique ordering )?</p>

<p>My understanding is that a) it might have a unique ordering if each cell depends on 3 of its neigh-boring cells b) it might have 3 orderings if each cell depends on 2 of its neigh-boring cells c) always more than 3 orderings if each cell depends only on one of its neigh-boring cells</p>

<p>2) any generic dependency between the ( total number of orderings ) versus ( dependency of a cell on number of its neighbours) ? Like if the dependency of a cell on the number of its neighbours increases then total number of possible orderings decrease?</p>

<p>3) Also, Is there any chance that the number of orderings can be zero? Where in it might become a chicken and egg problem?</p>

<matrices><dynamic-programming>
Ordering of sub problems in dynamic programming
coder101
# Ordering of sub problems in dynamic programming

(Asked by: username_0 on 2018-10-25)

1) Can every dynamic programming question be solved using 3 different orderings or can there be more than 3 or less than 3 ( like unique ordering )?

My understanding is that a) it might have a unique ordering if each cell depends on 3 of its neigh-boring cells b) it might have 3 orderings if each cell depends on 2 of its neigh-boring cells c) always more than 3 orderings if each cell depends only on one of its neigh-boring cells

2) any generic dependency between the ( total number of orderings ) versus ( dependency of a cell on number of its neighbours) ? Like if the dependency of a cell on the number of its neighbours increases then total number of possible orderings decrease?

3) Also, Is there any chance that the number of orderings can be zero? Where in it might become a chicken and egg problem?

**Tags:** matrices, dynamic-programming


---

## 1 answers

### Answer by username_1 on 2018-10-25. Score: 3

This is not a research level question. In any case DP is obtained by memoizing a recursion. If you start with an instance $I$ then the recursion generates several subproblems. You can obtain a dependency graph $G$ on these subproblems where each node is a subproblem and there is an arc $(I\_i,I\_j)$ if $I\_j$ calls $I\_i$. This dependency graph must necessarily be a directed acyclic graph (DAG) if the original recursion is correct. Now to evaluate the subproblems and eventually find the answer for $I$, one can use *any* topological ordering of $G$. In general there can be many topological orderings.


---

