Consider a table , where the elements , represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows:
for
for
Consider the following two algorithms to compute entries of . Assume that for both the algorithms, for all , has been initialized to 1.
Algorithm : For
For
Algorithm : For
For
For
If
Algorithm is said to be correct if and only if it calculates the correct values of , for all , (as per the recursive formulation) at the end of the execution of the algorithm .
Which one of the following statements is true?
- ABoth algorithms and are correct
- BAlgorithm is correct, but algorithm is incorrect
- CAlgorithm is correct, but algorithm is incorrect
- DBoth algorithms and are incorrect

