Question

Statement 1: When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don't take advantage of overlapping subproblems.
Statement 2: A greedy algorithm can be used to solve all the dynamic programming problems.

• A. Statement 1 is TRUE and Statement 2 is FALSE
• B. Statement 1 is FALSE and Statement 2 is TRUE
• C. Both Statements 1 and 2 are TRUE
• D. Both Statements 1 and 2 are FALSE

Hint:

Dynamic programming is useful when there are overlapping subproblems and optimal substructure, while greedy algorithms can be used for problems where a locally optimal solution leads to the globally optimal solution.

Answer 1

The Correct Option is A

- Statement 1: This is TRUE. Dynamic programming is a technique used to solve problems by breaking them down into overlapping subproblems and storing their solutions. It avoids redundant calculations and saves time compared to methods that don’t take advantage of overlapping subproblems, such as the brute force approach.
- Statement 2: This is FALSE. A greedy algorithm does not always provide the optimal solution for problems that can be solved by dynamic programming. While both greedy algorithms and dynamic programming solve optimization problems, the greedy approach makes locally optimal choices at each step, which doesn't always lead to the globally optimal solution as dynamic programming does.
Therefore, the correct answer is 1. Statement 1 is TRUE and Statement 2 is FALSE.