Given the following characteristics :

(i) Optimal substructure

(ii) Overlapping subproblems

(iii) Memorization

(iv) Decrease and conquer

Dynamic programming has the following characteristics :

The correct answer is Option 2.

Key Points

• Dynamic programming has the following characteristics:
  • Optimal substructure: This means that the solution to a problem can be constructed efficiently from solutions to its subproblems. For example, in the case of the shortest path problem, the shortest path from A to C through B can be derived from the shortest path from A to B and B to C.
  • Overlapping subproblems: This refers to the situation where the same subproblems are solved multiple times in the process of solving the overall problem. For example, in the Fibonacci sequence, the same Fibonacci numbers are computed multiple times.
  • Memoization: This technique involves storing the results of expensive function calls and reusing the cached result when the same inputs occur again. This helps in reducing the time complexity of algorithms that solve overlapping subproblems.

Additional Information

• Dynamic programming is often used for optimization problems where the goal is to find the best solution among many possibilities.
• Examples of problems that can be solved using dynamic programming include the knapsack problem, the traveling salesman problem, and sequence alignment in bioinformatics.
• Dynamic programming can be implemented in a top-down approach with memoization or a bottom-up approach with tabulation.
• It is an essential concept in computer science and is widely used in various fields such as operations research, economics, and artificial intelligence.