-4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.