1. Engineering
  2. Computer Science
  3. 4 in bottomup dynamic programming algorithm we need a traversal...

Question: 4 in bottomup dynamic programming algorithm we need a traversal...

Question details
4. In bottom-up dynamic programming algorithm, we need a traversal order such that all needed
subproblems are solved before solving the original problem. Suppose the recurrence relation for a
dynamic programming algorithm is of the form:
A(i, j) = f(A(i − 2, j− 2),A(i + 2, j+ 2))

A valid traversal order is:
[a] Solve A(i, j) for (i from 0 to n: for (j from 0 to n))
[b] Solve A(i, j) for (i from 0 to n-2: for (j from i+2 to n))
[c] Solve A(i, j) for (i from 0 to n-2: for (j from i to n))
[d] none of the above

Please explain why
Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution