3 votes

Consider the following steps:

$S_1$: Characterize the structure of an optimal solution

$S_2$: Compute the value of an optimal solution in bottom-up fashion

Which of the following step(s) is/are common to both dynamic programming and greedy algorithms?

- Only $S_1$
- Only $S_2$
- Both $S_1$ and $S_2$
- Neither $S_1$ nor $S_2$

1 vote

Ans. A

Both Dp and greedy algorithms find optimal substructure in the problem but only DP uses the bottom up approach.

Both Dp and greedy algorithms find optimal substructure in the problem but only DP uses the bottom up approach.