Question 3 ( 20 Marks) (a) marks) (adentity and explain the two properties of optimization problems that can be solved using the dynamic programming approach

Dynamic programming is a powerful method for solving optimization problems, particularly those that exhibit certain properties. The two key properties of optimization problems that can be effectively addressed using dynamic programming are: 1. **Optimal Substructure**: - This property means that an optimal solution to a problem can be constructed from optimal solutions to its subproblems. In other words, if you can break down a problem into smaller, simpler subproblems, and if the optimal solution to the overall problem can be derived from the optimal solutions of these subproblems, then the problem has an optimal substructure. - For example, in the case of the shortest path problem, if you know the shortest path from point A to point B, and you want to find the shortest path from point A to point C, you can use the shortest path from A to B as part of the solution to A to C. 2. **Overlapping Subproblems**: - This property indicates that the problem can be broken down into subproblems that are reused multiple times. Instead of solving the same subproblem repeatedly, dynamic programming solves each subproblem once and stores its result, thus avoiding the exponential time complexity that can arise from naive recursive solutions. - For instance, in the Fibonacci sequence calculation, the same Fibonacci numbers are calculated multiple times in a naive recursive approach. However, using dynamic programming, you can store the results of previously computed Fibonacci numbers and reuse them, significantly improving efficiency. In summary, dynamic programming is particularly useful for optimization problems that exhibit optimal substructure and overlapping subproblems, allowing for efficient computation and storage of intermediate results.