Dynamic Problem Approaches

Question 1

Memoization (Top-Down DP)

Answer 1

Start with the problem and break it into smaller subproblems, caching the results to avoid redundant calculations.

Example:
Fibonacci with memoization.

Question 2

Tabulation (Bottom-Up DP)

Answer 2

Iteratively solve smaller subproblems first and store their solutions in a table, building up to the solution of the main problem.

Example:
LCS, Knapsack problem.

Question 3

State Transition DP

Answer 3

Used in more complex problems where multiple states are involved (e.g., DP on trees, graphs, or paths).

Example:
Longest Increasing Subsequence.

Question 4

Greedy + DP

Answer 4

Combining greedy strategies with dynamic programming when greedy alone isn’t sufficient.

Example:
Weighted Job Scheduling with profit maximization.