The Gateway to Computer Science Excellence
+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?

  1. Only $S_1$
  2. Only $S_2$
  3. Both $S_1$ and $S_2$
  4. Neither $S_1$ nor $S_2$
in Algorithms by Veteran (432k points)
edited by | 210 views

2 Answers

+1 vote
Ans. A

Both Dp and greedy algorithms find optimal substructure in the problem but only DP uses the bottom up approach.
by (39 points)
0 votes
Opton (A): only S1

Because both greedy algo and dynamic programming finds the optimal solution for their problems but ,

only dynamic programming uses bottom-up approach

whereas,greedy algo uses top-bottom approach
by (303 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,394 answers
105,446 users