Count the number of distinct ways to reach the top of n stairs Read full solution .

Calculate the nth Fibonacci number using dynamic programming Read full solution .

Find maximum value that can be obtained with given weight capacity Read full solution .

Coin Change (Minimum Coins)

Find the minimum number of coins needed to make a given amount Read full solution .

Coin Change II (Number of Ways)

Count the number of ways to make a given amount using coins Read full solution .

Find maximum amount that can be robbed without robbing adjacent houses Read full solution .

Longest Common Subsequence

Find the length of the longest common subsequence between two strings Read full solution .

Longest Increasing Subsequence

Find the length of the longest increasing subsequence in an array Read full solution .

Count unique paths from top-left to bottom-right in a grid Read full solution .

Find minimum operations to convert one string to another Read full solution .

Regular Expression Matching

Implement regular expression matching with . and * Read full solution .

Return all possible ways to break a string into dictionary words Read full solution .

Dynamic Programming

Master dynamic programming patterns and optimization techniques.

Showing 12 of 12 questions

Filter:

Easy: 0 Medium: 0 Hard: 0

QUESTION	DIFFICULTY
Climbing Stairs Count the number of distinct ways to reach the top of n stairs	Easy
Fibonacci Numbers Calculate the nth Fibonacci number using dynamic programming	Easy
0/1 Knapsack Find maximum value that can be obtained with given weight capacity	Medium
Coin Change (Minimum Coins) Find the minimum number of coins needed to make a given amount	Medium
Coin Change II (Number of Ways) Count the number of ways to make a given amount using coins	Medium
House Robber Find maximum amount that can be robbed without robbing adjacent houses	Medium
Longest Common Subsequence Find the length of the longest common subsequence between two strings	Medium
Longest Increasing Subsequence Find the length of the longest increasing subsequence in an array	Medium
Unique Paths in Grid Count unique paths from top-left to bottom-right in a grid	Medium
Edit Distance Find minimum operations to convert one string to another	Hard
Regular Expression Matching Implement regular expression matching with . and *	Hard
Word Break II Return all possible ways to break a string into dictionary words	Hard

Overview

Dynamic Programming (DP) is a powerful technique for solving optimization problems by breaking them into overlapping subproblems. This section covers DP patterns and strategies for identifying and solving DP problems.

Key Concepts

Overlapping subproblems
Optimal substructure
Memoization (top-down)
Tabulation (bottom-up)
State definition
Transition equations

Common Patterns

Linear DP (1D array)
Grid DP (2D array)
Knapsack problems
Longest common subsequence
String matching
State machine DP

Common Problems

Easy

Climbing Stairs
House Robber
Maximum Subarray

Medium

Coin Change
Longest Increasing Subsequence
Unique Paths
Word Break
Partition Equal Subset Sum

Hard

Edit Distance
Regular Expression Matching
Burst Balloons
Longest Valid Parentheses

Practice Tips

Identify DP: Look for optimal substructure and overlapping subproblems
Define state: Clearly define what dp[i] or dp[i][j] represents
Find recurrence: Derive the transition equation
Base cases: Initialize boundary conditions correctly
Optimize space: Consider reducing dimensions if possible