Problems focusing on optimization using memoization and tabulation techniques.
- 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.)
- 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
- 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
- dp_max_sub_seq_sum - Maximum subsequence sum
- dp_dance_party - Dance party problem
- KnapSack2 - 0/1 Knapsack problem
- DungeonPrincess - Dungeon princess (minimum health path)
- 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