Project ForgeAlgorithms
Dynamic Programming & Greedy Algorithms
GATE 2009
Medium
The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j), using an array L[M,N], where M=m+1 and N=n+1, such that L[i,j]=l(i,j). Which one the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?
- AAll elements of L should be initialized to 0 for the values of l(i,j) to be properly computed.
- The values of l(i,j) may be computed in a row major order or column major order of L[M,N].
- CThe values of l(i,j) cannot be computed in either row major order or column major order of L[M,N].
- DL[p,q] needs to be computed before L[r,s] if either p<r or q<s.
Explanation
l(i,j) depends only on l(i-1,j), l(i,j-1), and l(i-1,j-1) — all with strictly smaller i or j. Scanning row-by-row left-to-right (row-major) always has these dependencies already computed, and by symmetry so does column-major. Either traversal order works.
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.