README.md

Dynamic Programming

Problems focusing on optimization using memoization and tabulation techniques.

Key Concepts Covered

• Memoization (top-down DP)
• Tabulation (bottom-up DP)
• State definition and transitions
• Optimal substructure
• Overlapping subproblems
• Space optimization techniques
• Classic DP patterns (knapsack, LCS, LIS, etc.)

Problems in this Directory

Classic DP Problems

• dp_fibnacci - Fibonacci using DP
• dp_fibonacci - Fibonacci variant
• dp_fib_lambda - Fibonacci with lambda
• dp_nstairs - Climb N stairs
• dp_nstairs2 - N stairs variant
• dp_perfectsquares - Minimum perfect squares to sum to N
• dp_perfect_sqrs - Perfect squares variant
• MinNumSquares - Minimum number of squares

Matrix DP

• dp_maxpath_matrix - Maximum path sum in matrix
• dp_totalways_matrix - Total ways to reach end
• dp_totalways_grid_obstacles - Grid paths with obstacles
• MaximumSubmatrixSum - Maximum sum submatrix (Kadane's 2D)
• MaximumSumSquareSubMatrix - Maximum sum square submatrix
• sumOfSubMatrices - Sum of all submatrices

Subsequence Problems

• dp_max_sub_seq_sum - Maximum subsequence sum

Game/Party Problems

• dp_dance_party - Dance party problem

Knapsack Variants

• KnapSack2 - 0/1 Knapsack problem

Special Problems

• DungeonPrincess - Dungeon princess (minimum health path)

Tips

• Identify the state and transitions first
• Start with recursive solution, then memoize
• Consider space optimization after solving
• Draw the DP table for better understanding
• Practice recognizing DP patterns