Overlapping Subproblems and Optimal Substructure in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does Overlapping Subproblems mean in dynamic programming?

It means the problem can be broken down into smaller subproblems that repeat multiple times. Instead of solving them again and again, we solve once and reuse the answer.

beginner

Explain Optimal Substructure in simple terms.

A problem has optimal substructure if the best solution can be made by combining the best solutions of its smaller parts.

intermediate

Why is Overlapping Subproblems important for dynamic programming?

Because it allows us to store results of subproblems and reuse them, saving time by avoiding repeated work.

beginner

Give an example of a problem that shows both overlapping subproblems and optimal substructure.

The Fibonacci sequence calculation: It has overlapping subproblems (fib(n-1), fib(n-2) repeat) and optimal substructure (fib(n) = fib(n-1) + fib(n-2)).

intermediate

How does memoization relate to overlapping subproblems?

Memoization saves answers of subproblems so when the same subproblem appears again, we use the saved answer instead of recalculating.

Which of the following best describes overlapping subproblems?

A Subproblems are completely different

B Subproblems repeat and can be reused

C Subproblems do not affect the main problem

D Subproblems are solved only once

Overlapping subproblems means the same smaller problems appear multiple times and can be reused.

What does optimal substructure allow us to do?

A Build the best solution from best smaller solutions

B Ignore smaller problems

C Solve only the largest problem

D Avoid breaking problems into parts

Optimal substructure means the best answer comes from combining best answers of smaller parts.

Which technique uses overlapping subproblems to improve efficiency?

A Greedy algorithm

B Brute force

C Sorting

D Memoization

Memoization stores results of repeated subproblems to avoid recalculating.

The Fibonacci sequence is an example of a problem with:

A Overlapping subproblems and optimal substructure

B No overlapping subproblems

C No optimal substructure

D Neither overlapping subproblems nor optimal substructure

Fibonacci has repeated subproblems and the solution builds from smaller solutions.

Why is dynamic programming better than simple recursion for problems with overlapping subproblems?

A It solves problems randomly

B It uses more memory without speed benefit

C It avoids repeated calculations by storing results

D It ignores subproblems

Dynamic programming stores answers to subproblems to reuse and save time.

Describe in your own words what overlapping subproblems and optimal substructure mean and why they matter in solving problems efficiently.

Think about breaking problems into parts and reusing answers.

Explain how memoization uses the concept of overlapping subproblems to improve performance.

Focus on saving and reusing answers.