23.3. Optimal Substructure Property

Try these first

1. 1.

   Define the Optimal Substructure Property in your own words.

   Hint

   Think of it as building a whole from its parts.

2. 2.

   Give an example of a problem that exhibits optimal substructure.

   Hint

   Consider functions that break down into simpler recursive calls.

3. 3.

   What does the Optimal Substructure Property allow us to do?

   • Ignore subproblems
   • Combine solutions of subproblems
   • Only solve the base case

   Hint

   Consider how solutions are related in recursive definitions.

4. 4.

   True or False: Dynamic programming can only be applied to problems with a single optimal solution.

   • True
   • False

   Hint

   Think about how overlapping solutions can exist.

5. 5.

   Design a dynamic programming algorithm to solve the knapsack problem. Outline the steps and structure the solution clearly.

   Hint

   Consider how you would break the problem down recursively before optimizing.

6. 6.

   Can you present a case where a greedy algorithm fails and dynamic programming succeeds? Describe the situation and why.

   Hint

   Analyze examples where local optimums lead to suboptimal solutions in broader contexts.