Skip to content

Dynamic Programming Roadmap.markdown

Latest commit

 

History

History
243 lines (230 loc) · 20.7 KB

Dynamic Programming Roadmap.markdown

File metadata and controls

243 lines (230 loc) · 20.7 KB
Raw

Dynamic Programming Roadmap: 500+ Problems to Mastery

Dynamic programming (DP) is a method for solving complex problems by breaking them into simpler subproblems, solving each subproblem once, and storing their solutions for reuse. This roadmap provides a structured path to master DP, covering 20 key patterns with over 500 problems sourced from platforms like LeetCode, Codeforces, AtCoder, and GeeksforGeeks. Problems are organized by difficulty (easy, medium, hard) to ensure progressive learning, incorporating advice from top coders to focus on pattern recognition and state optimization.

Key DP Patterns

The following 20 patterns cover the spectrum of DP problems, from foundational to advanced, based on common problem types identified in resources like AlgoMaster’s “20 Patterns to Master Dynamic Programming” and GitHub repositories.

  1. Fibonacci Sequence: Problems where the solution depends on smaller instances, often with a recursive relation like F(n) = F(n-1) + F(n-2).
  2. Kadane’s Algorithm: Optimizes contiguous subarray problems, such as finding the maximum subarray sum.
  3. 0/1 Knapsack: Select a subset of items with weight and value constraints, choosing each item at most once.
  4. Unbounded Knapsack: Similar to 0/1 Knapsack but allows multiple selections of items.
  5. Longest Common Subsequence (LCS): Find the longest subsequence present in two sequences in the same order.
  6. Longest Increasing Subsequence (LIS): Identify the longest subsequence with increasing values.
  7. Palindromic Subsequence: Find subsequences that read the same forwards and backwards.
  8. Edit Distance: Transform one sequence into another with minimum operations (insert, delete, substitute).
  9. Subset Sum: Determine if a subset of numbers sums to a target value.
  10. String Partition: Partition a string into substrings satisfying specific conditions.
  11. Catalan Numbers: Solve combinatorial problems like valid parentheses or binary search tree counts.
  12. Matrix Chain Multiplication: Optimize the order of matrix multiplications to minimize cost.
  13. Count Distinct Ways: Count the number of ways to achieve a goal, often combinatorial.
  14. DP on Grids: Navigate or optimize paths in a grid, considering multiple directions.
  15. DP on Trees: Solve problems on tree structures, computing values based on children or ancestors.
  16. DP on Graphs: Optimize paths or cycles in graphs, considering neighbor dependencies.
  17. Digit DP: Count or sum over a range of numbers, processing digits individually.
  18. Bitmasking DP: Use bitmasks to represent subsets or combinations for small sets.
  19. Probability DP: Calculate probabilities or expected values in random processes.
  20. State Machine DP: Model problems as state transitions to optimize sequences.

Roadmap with Problems

Below is the roadmap with problems for each pattern, organized by difficulty. Each pattern includes at least 25 problems, sourced from LeetCode, Codeforces, AtCoder, GeeksforGeeks, and GitHub repositories like rabiulcste/dynamic-programming. Problems are selected to cover variations and ensure a mix of classic and modern challenges.

1. Fibonacci Sequence

Description: Solve problems where the solution builds on smaller subproblems with a recursive relationship.

2. Kadane’s Algorithm

Description: Optimize problems involving contiguous subarrays, like maximum subarray sum.

3. 0/1 Knapsack

Description: Select items with weight and value constraints, each item used at most once.

4. Unbounded Knapsack

Description: Similar to 0/1 Knapsack but items can be selected multiple times.

5. Longest Common Subsequence (LCS)

Description: Find the longest subsequence present in two sequences.

6. Longest Increasing Subsequence (LIS)

Description: Find the longest subsequence with increasing values.

7. Palindromic Subsequence

Description: Find subsequences that are palindromes.