Pattern 17 of 22

Dynamic Programming Pattern: Template + 481 LeetCode Problems

Define a state, write the transition, and stop recomputing the same subproblem.

Easy: 12
Medium: 243
Hard: 226

What the dynamic programming pattern is

Dynamic programming applies when a problem has optimal substructure — the best answer is built from the best answers to smaller versions — and overlapping subproblems, meaning the naive recursion asks the same question many times. The work is entirely in the first line: choosing a state, the smallest set of numbers that fully describes a subproblem. Everything else follows, because the transition is just the answer to "what were the last choices that could have led here?" and the base case is the state small enough to answer without recursing. Write it as recursion with a cache first; that version is easier to get right because the transition reads like the problem statement. Convert to a bottom-up table only once it works, and only for the two things a table buys: no recursion limit, and the chance to notice that row i depends only on row i-1, which is what collapses an O(n·m) table into O(m) space.

When to use it

The problem asks for a count, a maximum, a minimum, or whether something is possible — not for the arrangement itself.
A greedy choice is provably wrong because a locally worse choice can lead to a better total.
The naive recursion is exponential and its calls repeat with identical arguments.
The input has an obvious ordering — a prefix, an index range, a remaining capacity — to index the state by.

The dynamic programming template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 481 problems listed below.

PythonDynamic Programming template

def rob(nums):
    """The canonical 1-D shape: dp[i] is the answer for the prefix nums[:i]."""
    if not nums:
        return 0

    dp = [0] * (len(nums) + 1)
    dp[1] = nums[0]                                   # base case

    for i in range(2, len(nums) + 1):                 # transition
        dp[i] = max(dp[i - 1],                        # skip nums[i - 1]
                    dp[i - 2] + nums[i - 1])          # take it, so skip its neighbour

    return dp[len(nums)]

Complexity characteristics

Time: O(states × transitions)
Auxiliary space: O(states), frequently reducible

The running time is the number of distinct states multiplied by the work done at each one, which is why choosing the state is the whole problem: a one-dimensional state over a prefix gives O(n), a two-dimensional state over two strings gives O(n·m), and a bitmask state over n items gives O(2ⁿ·n). Memoised recursion and a bottom-up table share the same complexity and differ only in constant factors and stack depth. The space often collapses — when row i depends only on row i−1, an O(n·m) table becomes O(m).

Eyes only

Meet the dynamic programming problem you did not practise.

In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.

Get Stealth Interview See pricing

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Technical interview · 45 minsolution.pyShared editor · Python 3Longest substring without repeatsMediumGiven a string s, return the length of the longest contiguous substring in which every character is unique.s = "abcabcbb"
→ 31def length_of_longest_substring(s: str) -> int:2 last_seen = {}3 left = best = 04 for right, ch in enumerate(s):5 if ch in last_seen and last_seen[ch] >= left:

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 Terra

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

Primary display

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

All 481 dynamic programming LeetCode problems

Every problem in the library the dynamic programming pattern applies to, grouped by LeetCode's own difficulty rating. 416 of the 481 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Easy (12)

Easy problems
No.	Problem	Topics
0070	Climbing Stairs	Memoization, Math, Dynamic Programming
0118	Pascal's Triangle	Array, Dynamic Programming
0119	Pascal's Triangle II	Array, Dynamic Programming
0121	Best Time to Buy and Sell Stock	Array, Dynamic Programming
0338	Counting Bits	Bit Manipulation, Dynamic Programming
0392	Is Subsequence	Two Pointers, String, Dynamic Programming
0509	Fibonacci Number	Recursion, Memoization, Math +1
0746	Min Cost Climbing Stairs	Array, Dynamic Programming
1137	N-th Tribonacci Number	Memoization, Math, Dynamic Programming
1025	Divisor Game	Brainteaser, Math, Dynamic Programming +1
1668	Maximum Repeating Substring	String, Dynamic Programming, String Matching
2900	Longest Unequal Adjacent Groups Subsequence I	Greedy, Array, String +1

Medium (243)

Medium problems
No.	Problem	Topics
0005	Longest Palindromic Substring	Two Pointers, String, Dynamic Programming
0022	Generate Parentheses	String, Dynamic Programming, Backtracking
0045	Jump Game II	Greedy, Array, Dynamic Programming
0053	Maximum Subarray	Array, Divide and Conquer, Dynamic Programming
0055	Jump Game	Greedy, Array, Dynamic Programming
0062	Unique Paths	Math, Dynamic Programming, Combinatorics
0063	Unique Paths II	Array, Dynamic Programming, Matrix
0064	Minimum Path Sum	Array, Dynamic Programming, Matrix
0072	Edit Distance	String, Dynamic Programming
0091	Decode Ways	String, Dynamic Programming
0095	Unique Binary Search Trees II	Tree, Binary Search Tree, Dynamic Programming +2
0096	Unique Binary Search Trees	Tree, Binary Search Tree, Math +2
0097	Interleaving String	String, Dynamic Programming
0120	Triangle	Array, Dynamic Programming
0122	Best Time to Buy and Sell Stock II	Greedy, Array, Dynamic Programming
0131	Palindrome Partitioning	String, Dynamic Programming, Backtracking
0139	Word Break	Trie, Memoization, Array +3
0152	Maximum Product Subarray	Array, Dynamic Programming
0198	House Robber	Array, Dynamic Programming
0213	House Robber II	Array, Dynamic Programming
0221	Maximal Square	Array, Dynamic Programming, Matrix
0241	Different Ways to Add Parentheses	Recursion, Memoization, Math +2
0264	Ugly Number II	Hash Table, Math, Dynamic Programming +1
0279	Perfect Squares	Breadth-First Search, Math, Dynamic Programming
0300	Longest Increasing Subsequence	Array, Binary Search, Dynamic Programming
0309	Best Time to Buy and Sell Stock with Cooldown	Array, Dynamic Programming
0313	Super Ugly Number	Array, Math, Dynamic Programming
0322	Coin Change	Breadth-First Search, Array, Dynamic Programming
0337	House Robber III	Tree, Depth-First Search, Dynamic Programming +1
0343	Integer Break	Math, Dynamic Programming
0357	Count Numbers with Unique Digits	Math, Dynamic Programming, Backtracking
0368	Largest Divisible Subset	Array, Math, Dynamic Programming +1
0375	Guess Number Higher or Lower II	Math, Dynamic Programming, Game Theory
0376	Wiggle Subsequence	Greedy, Array, Dynamic Programming
0377	Combination Sum IV	Array, Dynamic Programming
0396	Rotate Function	Array, Math, Dynamic Programming
0397	Integer Replacement	Greedy, Bit Manipulation, Memoization +1
0413	Arithmetic Slices	Array, Dynamic Programming, Sliding Window
0416	Partition Equal Subset Sum	Array, Dynamic Programming
0435	Non-overlapping Intervals	Greedy, Array, Dynamic Programming +1
0464	Can I Win	Bit Manipulation, Memoization, Math +3
0467	Unique Substrings in Wraparound String	String, Dynamic Programming
0473	Matchsticks to Square	Bit Manipulation, Array, Dynamic Programming +2
0474	Ones and Zeroes	Array, String, Dynamic Programming
0486	Predict the Winner	Recursion, Array, Math +2
0494	Target Sum	Array, Dynamic Programming, Backtracking
0516	Longest Palindromic Subsequence	String, Dynamic Programming
0518	Coin Change II	Array, Dynamic Programming
0526	Beautiful Arrangement	Bit Manipulation, Array, Dynamic Programming +2
0542	01 Matrix	Breadth-First Search, Array, Dynamic Programming +1
0553	Optimal Division	Array, Math, Dynamic Programming
0576	Out of Boundary Paths	Dynamic Programming
0583	Delete Operation for Two Strings	String, Dynamic Programming
0638	Shopping Offers	Bit Manipulation, Memoization, Array +3
0646	Maximum Length of Pair Chain	Greedy, Array, Dynamic Programming +1
0647	Palindromic Substrings	Two Pointers, String, Dynamic Programming
0650	2 Keys Keyboard	Math, Dynamic Programming
0673	Number of Longest Increasing Subsequence	Binary Indexed Tree, Segment Tree, Array +1
0678	Valid Parenthesis String	Stack, Greedy, String +1
0688	Knight Probability in Chessboard	Dynamic Programming
0698	Partition to K Equal Sum Subsets	Bit Manipulation, Memoization, Array +3
0712	Minimum ASCII Delete Sum for Two Strings	String, Dynamic Programming
0714	Best Time to Buy and Sell Stock with Transaction Fee	Greedy, Array, Dynamic Programming
0718	Maximum Length of Repeated Subarray	Array, Binary Search, Dynamic Programming +3
0740	Delete and Earn	Array, Hash Table, Dynamic Programming
0787	Cheapest Flights Within K Stops	Depth-First Search, Breadth-First Search, Graph +3
0790	Domino and Tromino Tiling	Dynamic Programming
0918	Maximum Sum Circular Subarray	Queue, Array, Divide and Conquer +2
1143	Longest Common Subsequence	String, Dynamic Programming
1372	Longest ZigZag Path in a Binary Tree	Tree, Depth-First Search, Dynamic Programming +1
1493	Longest Subarray of 1's After Deleting One Element	Array, Dynamic Programming, Sliding Window
0256	Paint HousePremium	Array, Dynamic Programming
0276	Paint FencePremium	Dynamic Programming
0294	Flip Game IIPremium	Memoization, Math, Dynamic Programming +2
0333	Largest BST SubtreePremium	Tree, Depth-First Search, Binary Search Tree +2
0351	Android Unlock PatternsPremium	Bit Manipulation, Dynamic Programming, Backtracking +1
0361	Bomb EnemyPremium	Array, Dynamic Programming, Matrix
0418	Sentence Screen FittingPremium	Array, String, Dynamic Programming
0487	Max Consecutive Ones IIPremium	Array, Dynamic Programming, Sliding Window
0562	Longest Line of Consecutive One in MatrixPremium	Array, Dynamic Programming, Matrix
0634	Find the Derangement of An ArrayPremium	Math, Dynamic Programming, Combinatorics
0651	4 Keys KeyboardPremium	Math, Dynamic Programming
0750	Number Of Corner RectanglesPremium	Array, Math, Dynamic Programming +1
0764	Largest Plus Sign	Array, Dynamic Programming
0788	Rotated Digits	Math, Dynamic Programming
0792	Number of Matching Subsequences	Trie, Array, Hash Table +4
0799	Champagne Tower	Dynamic Programming
0808	Soup Servings	Math, Dynamic Programming, Probability and Statistics
0813	Largest Sum of Averages	Array, Dynamic Programming, Prefix Sum
0823	Binary Trees With Factors	Array, Hash Table, Dynamic Programming +1
0837	New 21 Game	Math, Dynamic Programming, Sliding Window +1
0838	Push Dominoes	Two Pointers, String, Dynamic Programming
0845	Longest Mountain in Array	Array, Two Pointers, Dynamic Programming +1
0873	Length of Longest Fibonacci Subsequence	Array, Hash Table, Dynamic Programming
0877	Stone Game	Array, Math, Dynamic Programming +1
0894	All Possible Full Binary Trees	Tree, Recursion, Memoization +2
0898	Bitwise ORs of Subarrays	Bit Manipulation, Array, Dynamic Programming
0907	Sum of Subarray Minimums	Stack, Array, Dynamic Programming +1
0926	Flip String to Monotone Increasing	String, Dynamic Programming
0931	Minimum Falling Path Sum	Array, Dynamic Programming, Matrix
0935	Knight Dialer	Dynamic Programming
0978	Longest Turbulent Subarray	Array, Dynamic Programming, Sliding Window
0983	Minimum Cost For Tickets	Array, Dynamic Programming
1014	Best Sightseeing Pair	Array, Dynamic Programming
1024	Video Stitching	Greedy, Array, Dynamic Programming
1027	Longest Arithmetic Subsequence	Array, Hash Table, Binary Search +1
1031	Maximum Sum of Two Non-Overlapping Subarrays	Array, Dynamic Programming, Sliding Window
1035	Uncrossed Lines	Array, Dynamic Programming
1039	Minimum Score Triangulation of Polygon	Array, Dynamic Programming
1043	Partition Array for Maximum Sum	Array, Dynamic Programming
1048	Longest String Chain	Array, Hash Table, Two Pointers +3
1049	Last Stone Weight II	Array, Dynamic Programming
1062	Longest Repeating SubstringPremium	String, Binary Search, Dynamic Programming +3
1066	Campus Bikes IIPremium	Bit Manipulation, Array, Dynamic Programming +2
1105	Filling Bookcase Shelves	Array, Dynamic Programming
1130	Minimum Cost Tree From Leaf Values	Stack, Greedy, Array +2
1139	Largest 1-Bordered Square	Array, Dynamic Programming, Matrix
1140	Stone Game II	Array, Math, Dynamic Programming +2
1155	Number of Dice Rolls With Target Sum	Dynamic Programming
1162	As Far from Land as Possible	Breadth-First Search, Array, Dynamic Programming +1
1182	Shortest Distance to Target ColorPremium	Array, Binary Search, Dynamic Programming
1186	Maximum Subarray Sum with One Deletion	Array, Dynamic Programming
1191	K-Concatenation Maximum Sum	Array, Dynamic Programming
1218	Longest Arithmetic Subsequence of Given Difference	Array, Hash Table, Dynamic Programming
1227	Airplane Seat Assignment Probability	Brainteaser, Math, Dynamic Programming +1
1230	Toss Strange CoinsPremium	Array, Math, Dynamic Programming +1
1262	Greatest Sum Divisible by Three	Greedy, Array, Dynamic Programming +1
1277	Count Square Submatrices with All Ones	Array, Dynamic Programming, Matrix
1334	Find the City With the Smallest Number of Neighbors at a Threshold Distance	Graph, Dynamic Programming, Shortest Path
1387	Sort Integers by The Power Value	Memoization, Dynamic Programming, Sorting
1395	Count Number of Teams	Binary Indexed Tree, Segment Tree, Array +1
1477	Find Two Non-overlapping Sub-arrays Each With Target Sum	Array, Hash Table, Binary Search +2
1504	Count Submatrices With All Ones	Stack, Array, Dynamic Programming +2
1524	Number of Sub-arrays With Odd Sum	Array, Math, Dynamic Programming +1
1525	Number of Good Ways to Split a String	Bit Manipulation, Hash Table, String +1
1567	Maximum Length of Subarray With Positive Product	Greedy, Array, Dynamic Programming
1578	Minimum Time to Make Rope Colorful	Greedy, Array, String +1
1594	Maximum Non Negative Product in a Matrix	Array, Dynamic Programming, Matrix
1621	Number of Sets of K Non-Overlapping Line Segments	Math, Dynamic Programming, Combinatorics
1626	Best Team With No Conflicts	Array, Dynamic Programming, Sorting
1638	Count Substrings That Differ by One Character	Hash Table, String, Dynamic Programming +1
1641	Count Sorted Vowel Strings	Math, Dynamic Programming, Combinatorics
1653	Minimum Deletions to Make String Balanced	Stack, String, Dynamic Programming
1654	Minimum Jumps to Reach Home	Breadth-First Search, Array, Dynamic Programming
1682	Longest Palindromic Subsequence IIPremium	String, Dynamic Programming
1690	Stone Game VII	Array, Math, Dynamic Programming +1
1696	Jump Game VI	Queue, Array, Dynamic Programming +2
1746	Maximum Subarray Sum After One OperationPremium	Array, Dynamic Programming
1749	Maximum Absolute Sum of Any Subarray	Array, Dynamic Programming
1774	Closest Dessert Cost	Array, Dynamic Programming, Backtracking
1786	Number of Restricted Paths From First to Last Node	Graph, Topological Sort, Dynamic Programming +2
1824	Minimum Sideway Jumps	Greedy, Array, Dynamic Programming
1871	Jump Game VII	String, Dynamic Programming, Prefix Sum +1
1884	Egg Drop With 2 Eggs and N Floors	Math, Dynamic Programming
1888	Minimum Number of Flips to Make the Binary String Alternating	String, Dynamic Programming, Sliding Window
1908	Game of NimPremium	Bit Manipulation, Brainteaser, Array +3
1911	Maximum Alternating Subsequence Sum	Array, Dynamic Programming
1937	Maximum Number of Points with Cost	Array, Dynamic Programming, Matrix
1947	Maximum Compatibility Score Sum	Bit Manipulation, Array, Dynamic Programming +2
1959	Minimum Total Space Wasted With K Resizing Operations	Array, Dynamic Programming
1976	Number of Ways to Arrive at Destination	Graph, Topological Sort, Dynamic Programming +1
1981	Minimize the Difference Between Target and Chosen Elements	Array, Dynamic Programming, Matrix
1986	Minimum Number of Work Sessions to Finish the Tasks	Bit Manipulation, Array, Dynamic Programming +2
1997	First Day Where You Have Been in All the Rooms	Array, Dynamic Programming
2002	Maximum Product of the Length of Two Palindromic Subsequences	Bit Manipulation, String, Dynamic Programming +2
2008	Maximum Earnings From Taxi	Array, Hash Table, Binary Search +2
2036	Maximum Alternating Subarray SumPremium	Array, Dynamic Programming
2052	Minimum Cost to Separate Sentence Into RowsPremium	Array, Dynamic Programming
2054	Two Best Non-Overlapping Events	Array, Binary Search, Dynamic Programming +2
2063	Vowels of All Substrings	Math, String, Dynamic Programming +1
2086	Minimum Number of Food Buckets to Feed the Hamsters	Greedy, String, Dynamic Programming
2100	Find Good Days to Rob the Bank	Array, Dynamic Programming, Prefix Sum
2110	Number of Smooth Descent Periods of a Stock	Array, Math, Two Pointers +2
2140	Solving Questions With Brainpower	Array, Dynamic Programming
2152	Minimum Number of Lines to Cover PointsPremium	Bit Manipulation, Geometry, Array +5
2184	Number of Ways to Build Sturdy Brick WallPremium	Bit Manipulation, Array, Dynamic Programming +1
2189	Number of Ways to Build House of CardsPremium	Math, Dynamic Programming
2222	Number of Ways to Select Buildings	String, Dynamic Programming, Prefix Sum
2266	Count Number of Texts	Hash Table, Math, String +1
2291	Maximum Profit From Trading StocksPremium	Array, Dynamic Programming
2297	Jump Game VIIIPremium	Stack, Graph, Array +3
2304	Minimum Path Cost in a Grid	Array, Dynamic Programming, Matrix
2305	Fair Distribution of Cookies	Bit Manipulation, Array, Dynamic Programming +2
2310	Sum of Numbers With Units Digit K	Greedy, Math, Dynamic Programming +1
2311	Longest Binary Subsequence Less Than or Equal to K	Greedy, Memoization, String +1
2320	Count Number of Ways to Place Houses	Dynamic Programming
2327	Number of People Aware of a Secret	Queue, Dynamic Programming, Simulation
2369	Check if There is a Valid Partition For The Array	Array, Dynamic Programming
2370	Longest Ideal Subsequence	Hash Table, String, Dynamic Programming
2378	Choose Edges to Maximize Score in a TreePremium	Tree, Depth-First Search, Dynamic Programming
2380	Time Needed to Rearrange a Binary String	String, Dynamic Programming, Simulation
2393	Count Strictly Increasing SubarraysPremium	Array, Math, Dynamic Programming
2400	Number of Ways to Reach a Position After Exactly k Steps	Math, Dynamic Programming, Combinatorics
2420	Find All Good Indices	Array, Dynamic Programming, Prefix Sum
2431	Maximize Total Tastiness of Purchased FruitsPremium	Array, Dynamic Programming
2436	Minimum Split Into Subarrays With GCD Greater Than OnePremium	Greedy, Array, Math +2
2439	Minimize Maximum of Array	Greedy, Array, Binary Search +2
2464	Minimum Subarrays in a Valid SplitPremium	Array, Math, Dynamic Programming +1
2466	Count Ways To Build Good Strings	Dynamic Programming
2495	Number of Subarrays Having Even ProductPremium	Array, Math, Dynamic Programming
2501	Longest Square Streak in an Array	Array, Hash Table, Binary Search +2
2510	Check if There is a Path With Equal Number of 0's And 1'sPremium	Array, Dynamic Programming, Matrix
2522	Partition String Into Substrings With Values at Most K	Greedy, String, Dynamic Programming
2533	Number of Good Binary StringsPremium	Dynamic Programming
2556	Disconnect Path in a Binary Matrix by at Most One Flip	Depth-First Search, Breadth-First Search, Array +2
2560	House Robber IV	Greedy, Array, Binary Search +1
2571	Minimum Operations to Reduce an Integer to 0	Greedy, Bit Manipulation, Dynamic Programming
2572	Count the Number of Square-Free Subsets	Bit Manipulation, Array, Math +2
2597	The Number of Beautiful Subsets	Array, Hash Table, Math +4
2606	Find the Substring With Maximum Cost	Array, Hash Table, String +1
2616	Minimize the Maximum Difference of Pairs	Greedy, Array, Binary Search +2
2638	Count the Number of K-Free SubsetsPremium	Array, Math, Dynamic Programming +2
2645	Minimum Additions to Make Valid String	Stack, Greedy, String +1
2673	Make Costs of Paths Equal in a Binary Tree	Greedy, Tree, Array +2
2684	Maximum Number of Moves in a Grid	Array, Dynamic Programming, Matrix
2707	Extra Characters in a String	Trie, Array, Hash Table +2
2708	Maximum Strength of a Group	Greedy, Bit Manipulation, Array +4
2712	Minimum Cost to Make All Characters Equal	Greedy, String, Dynamic Programming
2741	Special Permutations	Bit Manipulation, Array, Dynamic Programming +1
2745	Construct the Longest New String	Greedy, Brainteaser, Math +1
2746	Decremental String Concatenation	Array, String, Dynamic Programming
2750	Ways to Split Array Into Good Subarrays	Array, Math, Dynamic Programming
2767	Partition String Into Minimum Beautiful Substrings	Hash Table, String, Dynamic Programming +1
2770	Maximum Number of Jumps to Reach the Last Index	Array, Dynamic Programming
2771	Longest Non-decreasing Subarray From Two Arrays	Array, Dynamic Programming
2786	Visit Array Positions to Maximize Score	Array, Dynamic Programming
2787	Ways to Express an Integer as Sum of Powers	Dynamic Programming
2811	Check if it is Possible to Split Array	Greedy, Array, Dynamic Programming
2826	Sorting Three Groups	Array, Binary Search, Dynamic Programming
2830	Maximize the Profit as the Salesman	Array, Hash Table, Binary Search +2
2850	Minimum Moves to Spread Stones Over Grid	Breadth-First Search, Array, Dynamic Programming +1
2892	Minimizing Array After Replacing Pairs With Their ProductPremium	Greedy, Array, Dynamic Programming
2896	Apply Operations to Make Two Strings Equal	String, Dynamic Programming
2901	Longest Unequal Adjacent Groups Subsequence II	Array, String, Dynamic Programming
2915	Length of the Longest Subsequence That Sums to Target	Array, Dynamic Programming
2919	Minimum Increment Operations to Make Array Beautiful	Array, Dynamic Programming
2925	Maximum Score After Applying Operations on a Tree	Tree, Depth-First Search, Dynamic Programming
2930	Number of Strings Which Can Be Rearranged to Contain Substring	Math, Dynamic Programming, Combinatorics
2944	Minimum Number of Coins for Fruits	Queue, Array, Dynamic Programming +2
2957	Remove Adjacent Almost-Equal Characters	Greedy, String, Dynamic Programming
2979	Most Expensive Item That Can Not Be BoughtPremium	Math, Dynamic Programming, Number Theory
2992	Number of Self-Divisible PermutationsPremium	Bit Manipulation, Array, Math +4
2998	Minimum Number of Operations to Make X and Y Equal	Breadth-First Search, Memoization, Dynamic Programming

Hard (226)

Hard problems
No.	Problem	Topics
0010	Regular Expression Matching	Recursion, String, Dynamic Programming
0032	Longest Valid Parentheses	Stack, String, Dynamic Programming
0042	Trapping Rain Water	Stack, Array, Two Pointers +2
0044	Wildcard Matching	Greedy, Recursion, String +1
0085	Maximal Rectangle	Stack, Array, Dynamic Programming +2
0087	Scramble String	String, Dynamic Programming
0115	Distinct Subsequences	String, Dynamic Programming
0123	Best Time to Buy and Sell Stock III	Array, Dynamic Programming
0124	Binary Tree Maximum Path Sum	Tree, Depth-First Search, Dynamic Programming +1
0132	Palindrome Partitioning II	String, Dynamic Programming
0140	Word Break II	Trie, Memoization, Array +4
0174	Dungeon Game	Array, Dynamic Programming, Matrix
0188	Best Time to Buy and Sell Stock IV	Array, Dynamic Programming
0233	Number of Digit One	Recursion, Math, Dynamic Programming
0312	Burst Balloons	Array, Dynamic Programming
0329	Longest Increasing Path in a Matrix	Depth-First Search, Breadth-First Search, Graph +5
0354	Russian Doll Envelopes	Array, Binary Search, Dynamic Programming +1
0403	Frog Jump	Array, Dynamic Programming
0410	Split Array Largest Sum	Greedy, Array, Binary Search +2
0446	Arithmetic Slices II - Subsequence	Array, Dynamic Programming
0458	Poor Pigs	Math, Dynamic Programming, Combinatorics
0466	Count The Repetitions	String, Dynamic Programming
0472	Concatenated Words	Depth-First Search, Trie, Array +3
0488	Zuma Game	Stack, Breadth-First Search, Memoization +2
0514	Freedom Trail	Depth-First Search, Breadth-First Search, String +1
0546	Remove Boxes	Memoization, Array, Dynamic Programming
0552	Student Attendance Record II	Dynamic Programming
0600	Non-negative Integers without Consecutive Ones	Dynamic Programming
0629	K Inverse Pairs Array	Dynamic Programming
0639	Decode Ways II	String, Dynamic Programming
0664	Strange Printer	String, Dynamic Programming
0689	Maximum Sum of 3 Non-Overlapping Subarrays	Array, Dynamic Programming, Prefix Sum +1
0691	Stickers to Spell Word	Bit Manipulation, Memoization, Array +5
0730	Count Different Palindromic Subsequences	String, Dynamic Programming
0741	Cherry Pickup	Array, Dynamic Programming, Matrix
1235	Maximum Profit in Job Scheduling	Array, Binary Search, Dynamic Programming +1
0265	Paint House IIPremium	Array, Dynamic Programming
0465	Optimal Account BalancingPremium	Bit Manipulation, Array, Dynamic Programming +2
0471	Encode String with Shortest LengthPremium	String, Dynamic Programming
0568	Maximum Vacation DaysPremium	Array, Dynamic Programming, Matrix
0656	Coin PathPremium	Array, Dynamic Programming
0727	Minimum Window SubsequencePremium	String, Dynamic Programming, Sliding Window
0773	Sliding Puzzle	Breadth-First Search, Memoization, Array +3
0801	Minimum Swaps To Make Sequences Increasing	Array, Dynamic Programming
0805	Split Array With Same Average	Bit Manipulation, Array, Math +2
0818	Race Car	Dynamic Programming
0828	Count Unique Characters of All Substrings of a Given String	Hash Table, String, Dynamic Programming
0834	Sum of Distances in Tree	Tree, Depth-First Search, Graph +1
0847	Shortest Path Visiting All Nodes	Bit Manipulation, Breadth-First Search, Graph +2
0871	Minimum Number of Refueling Stops	Greedy, Array, Dynamic Programming +1
0879	Profitable Schemes	Array, Dynamic Programming
0887	Super Egg Drop	Math, Binary Search, Dynamic Programming
0902	Numbers At Most N Given Digit Set	Array, Math, String +2
0903	Valid Permutations for DI Sequence	String, Dynamic Programming, Prefix Sum
0913	Cat and Mouse	Graph, Topological Sort, Memoization +3
0920	Number of Music Playlists	Math, Dynamic Programming, Combinatorics
0940	Distinct Subsequences II	String, Dynamic Programming
0943	Find the Shortest Superstring	Bit Manipulation, Array, String +2
0956	Tallest Billboard	Array, Dynamic Programming
0960	Delete Columns to Make Sorted III	Array, String, Dynamic Programming
0964	Least Operators to Express Number	Memoization, Math, Dynamic Programming
0968	Binary Tree Cameras	Tree, Depth-First Search, Dynamic Programming +1
0975	Odd Even Jump	Stack, Array, Dynamic Programming +3
0996	Number of Squareful Arrays	Bit Manipulation, Array, Hash Table +4
1000	Minimum Cost to Merge Stones	Array, Dynamic Programming, Prefix Sum
1012	Numbers With Repeated Digits	Math, Dynamic Programming
1067	Digit Count in RangePremium	Math, Dynamic Programming
1092	Shortest Common Supersequence	String, Dynamic Programming
1125	Smallest Sufficient Team	Bit Manipulation, Array, Dynamic Programming +1
1147	Longest Chunked Palindrome Decomposition	Greedy, Two Pointers, String +3
1187	Make Array Strictly Increasing	Array, Binary Search, Dynamic Programming +1
1216	Valid Palindrome IIIPremium	String, Dynamic Programming
1220	Count Vowels Permutation	Dynamic Programming
1223	Dice Roll Simulation	Array, Dynamic Programming
1246	Palindrome RemovalPremium	Array, Dynamic Programming
1255	Maximum Score Words Formed by Letters	Bit Manipulation, Array, Hash Table +5
1259	Handshakes That Don't CrossPremium	Math, Dynamic Programming
1269	Number of Ways to Stay in the Same Place After Some Steps	Dynamic Programming
1278	Palindrome Partitioning III	String, Dynamic Programming
1289	Minimum Falling Path Sum II	Array, Dynamic Programming, Matrix
1301	Number of Paths with Max Score	Array, Dynamic Programming, Matrix
1312	Minimum Insertion Steps to Make a String Palindrome	String, Dynamic Programming
1320	Minimum Distance to Type a Word Using Two Fingers	String, Dynamic Programming
1326	Minimum Number of Taps to Open to Water a Garden	Greedy, Array, Dynamic Programming
1335	Minimum Difficulty of a Job Schedule	Array, Dynamic Programming
1340	Jump Game V	Array, Dynamic Programming, Sorting
1349	Maximum Students Taking Exam	Bit Manipulation, Array, Dynamic Programming +2
1359	Count All Valid Pickup and Delivery Options	Math, Dynamic Programming, Combinatorics
1363	Largest Multiple of Three	Greedy, Array, Math +2
1373	Maximum Sum BST in Binary Tree	Tree, Depth-First Search, Binary Search Tree +2
1388	Pizza With 3n Slices	Greedy, Array, Dynamic Programming +1
1397	Find All Good Strings	String, Dynamic Programming, String Matching
1402	Reducing Dishes	Greedy, Array, Dynamic Programming +1
1406	Stone Game III	Array, Math, Dynamic Programming +1
1411	Number of Ways to Paint N × 3 Grid	Dynamic Programming
1416	Restore The Array	String, Dynamic Programming
1420	Build Array Where You Can Find The Maximum Exactly K Comparisons	Dynamic Programming, Prefix Sum
1425	Constrained Subsequence Sum	Queue, Array, Dynamic Programming +3
1434	Number of Ways to Wear Different Hats to Each Other	Bit Manipulation, Array, Dynamic Programming +1
1444	Number of Ways of Cutting a Pizza	Memoization, Array, Dynamic Programming +2
1449	Form Largest Integer With Digits That Add up to Target	Array, Dynamic Programming
1458	Max Dot Product of Two Subsequences	Array, Dynamic Programming
1463	Cherry Pickup II	Array, Dynamic Programming, Matrix
1467	Probability of a Two Boxes Having The Same Number of Distinct Balls	Array, Math, Dynamic Programming +3
1473	Paint House III	Array, Dynamic Programming
1478	Allocate Mailboxes	Array, Math, Dynamic Programming +1
1483	Kth Ancestor of a Tree Node	Bit Manipulation, Tree, Depth-First Search +4
1494	Parallel Courses II	Bit Manipulation, Graph, Dynamic Programming +1
1510	Stone Game IV	Math, Dynamic Programming, Game Theory
1526	Minimum Number of Increments on Subarrays to Form a Target Array	Stack, Greedy, Array +2
1531	String Compression II	String, Dynamic Programming
1537	Get the Maximum Score	Greedy, Array, Two Pointers +1
1547	Minimum Cost to Cut a Stick	Array, Dynamic Programming, Sorting
1548	The Most Similar Path in a GraphPremium	Graph, Dynamic Programming
1553	Minimum Number of Days to Eat N Oranges	Memoization, Dynamic Programming
1563	Stone Game V	Array, Math, Dynamic Programming +1
1569	Number of Ways to Reorder Array to Get Same BST	Tree, Union Find, Binary Search Tree +7
1575	Count All Possible Routes	Memoization, Array, Dynamic Programming
1595	Minimum Cost to Connect Two Groups of Points	Bit Manipulation, Array, Dynamic Programming +2
1611	Minimum One Bit Operations to Make Integers Zero	Bit Manipulation, Memoization, Dynamic Programming
1617	Count Subtrees With Max Distance Between Cities	Bit Manipulation, Tree, Dynamic Programming +2
1639	Number of Ways to Form a Target String Given a Dictionary	Array, String, Dynamic Programming
1643	Kth Smallest Instructions	Array, Math, Dynamic Programming +1
1655	Distribute Repeating Integers	Bit Manipulation, Array, Dynamic Programming +2
1659	Maximize Grid Happiness	Bit Manipulation, Memoization, Dynamic Programming +1
1671	Minimum Number of Removals to Make Mountain Array	Greedy, Array, Binary Search +1
1681	Minimum Incompatibility	Bit Manipulation, Array, Dynamic Programming +1
1687	Delivering Boxes from Storage to Ports	Segment Tree, Queue, Array +4
1691	Maximum Height by Stacking Cuboids	Array, Dynamic Programming, Sorting
1692	Count Ways to Distribute CandiesPremium	Dynamic Programming
1714	Sum Of Special Evenly-Spaced Elements In ArrayPremium	Array, Dynamic Programming
1723	Find Minimum Time to Finish All Jobs	Bit Manipulation, Array, Dynamic Programming +2
1728	Cat and Mouse II	Graph, Topological Sort, Memoization +5
1735	Count Ways to Make Array With Product	Array, Math, Dynamic Programming +2
1745	Palindrome Partitioning IV	String, Dynamic Programming
1751	Maximum Number of Events That Can Be Attended II	Array, Binary Search, Dynamic Programming +1
1755	Closest Subsequence Sum	Bit Manipulation, Array, Two Pointers +3
1770	Maximum Score from Performing Multiplication Operations	Array, Dynamic Programming
1771	Maximize Palindrome Length From Subsequences	String, Dynamic Programming
1787	Make the XOR of All Segments Equal to Zero	Bit Manipulation, Array, Dynamic Programming
1799	Maximize Score After N Operations	Bit Manipulation, Array, Math +4
1815	Maximum Number of Groups Getting Fresh Donuts	Bit Manipulation, Memoization, Array +2
1857	Largest Color Value in a Directed Graph	Graph, Topological Sort, Memoization +3
1866	Number of Ways to Rearrange Sticks With K Sticks Visible	Math, Dynamic Programming, Combinatorics
1872	Stone Game VIII	Array, Math, Dynamic Programming +2
1879	Minimum XOR Sum of Two Arrays	Bit Manipulation, Array, Dynamic Programming +1
1883	Minimum Skips to Arrive at Meeting On Time	Array, Dynamic Programming
1896	Minimum Cost to Change the Final Value of Expression	Stack, Math, String +1
1900	The Earliest and Latest Rounds Where Players Compete	Memoization, Dynamic Programming
1916	Count Ways to Build Rooms in an Ant Colony	Tree, Graph, Topological Sort +3
1928	Minimum Cost to Reach Destination in Time	Graph, Array, Dynamic Programming
1931	Painting a Grid With Three Different Colors	Dynamic Programming
1955	Count Number of Special Subsequences	Array, Dynamic Programming
1977	Number of Ways to Separate Numbers	String, Dynamic Programming, Suffix Array
1987	Number of Unique Good Subsequences	String, Dynamic Programming
1994	The Number of Good Subsets	Bit Manipulation, Array, Hash Table +5
2003	Smallest Missing Genetic Value in Each Subtree	Tree, Depth-First Search, Union Find +1
2005	Subtree Removal Game with Fibonacci TreePremium	Tree, Math, Dynamic Programming +2
2019	The Score of Students Solving Math Expression	Stack, Memoization, Array +4
2035	Partition Array Into Two Arrays to Minimize Sum Difference	Bit Manipulation, Array, Two Pointers +4
2050	Parallel Courses III	Graph, Topological Sort, Array +1
2060	Check if an Original String Exists Given Two Encoded Strings	String, Dynamic Programming
2088	Count Fertile Pyramids in a Land	Array, Dynamic Programming, Matrix
2143	Choose Numbers From Two Arrays in RangePremium	Array, Dynamic Programming
2147	Number of Ways to Divide a Long Corridor	Math, String, Dynamic Programming
2163	Minimum Difference in Sums After Removal of Elements	Array, Dynamic Programming, Heap (Priority Queue)
2167	Minimum Time to Remove All Cars Containing Illegal Goods	String, Dynamic Programming
2172	Maximum AND Sum of Array	Bit Manipulation, Array, Dynamic Programming +1
2188	Minimum Time to Finish the Race	Array, Dynamic Programming
2209	Minimum White Tiles After Covering With Carpets	String, Dynamic Programming, Prefix Sum
2218	Maximum Value of K Coins From Piles	Array, Dynamic Programming, Prefix Sum
2247	Maximum Cost of Trip With K HighwaysPremium	Bit Manipulation, Graph, Dynamic Programming +1
2262	Total Appeal of A String	Hash Table, String, Dynamic Programming
2263	Make Array Non-decreasing or Non-increasingPremium	Greedy, Dynamic Programming
2267	Check if There Is a Valid Parentheses String Path	Array, Dynamic Programming, Matrix
2272	Substring With Largest Variance	Array, Dynamic Programming
2312	Selling Pieces of Wood	Memoization, Array, Dynamic Programming
2313	Minimum Flips in Binary Tree to Get ResultPremium	Tree, Depth-First Search, Dynamic Programming +1
2318	Number of Distinct Roll Sequences	Memoization, Dynamic Programming
2321	Maximum Score Of Spliced Array	Array, Dynamic Programming
2328	Number of Increasing Paths in a Grid	Depth-First Search, Breadth-First Search, Graph +5
2338	Count the Number of Ideal Arrays	Math, Dynamic Programming, Combinatorics +1
2355	Maximum Number of Books You Can TakePremium	Stack, Array, Dynamic Programming +1
2361	Minimum Costs Using the Train LinePremium	Array, Dynamic Programming
2376	Count Special Integers	Math, Dynamic Programming
2403	Minimum Time to Kill All MonstersPremium	Bit Manipulation, Array, Dynamic Programming +1
2407	Longest Increasing Subsequence II	Binary Indexed Tree, Segment Tree, Queue +4
2430	Maximum Deletions on a String	String, Dynamic Programming, String Matching +2
2435	Paths in Matrix Whose Sum Is Divisible by K	Array, Dynamic Programming, Matrix
2463	Minimum Total Distance Traveled	Array, Dynamic Programming, Sorting
2472	Maximum Number of Non-overlapping Palindrome Substrings	Greedy, Two Pointers, String +1
2478	Number of Beautiful Partitions	String, Dynamic Programming, Prefix Sum
2484	Count Palindromic Subsequences	String, Dynamic Programming
2518	Number of Great Partitions	Array, Dynamic Programming
2538	Difference Between Maximum and Minimum Price Sum	Tree, Depth-First Search, Array +1
2547	Minimum Cost to Split an Array	Array, Hash Table, Dynamic Programming +1
2552	Count Increasing Quadruplets	Binary Indexed Tree, Array, Dynamic Programming +2
2573	Find the String with LCP	Greedy, Union Find, Array +3
2581	Count Number of Possible Root Nodes	Tree, Depth-First Search, Array +2
2585	Number of Ways to Earn Points	Array, Dynamic Programming
2617	Minimum Number of Visited Cells in a Grid	Stack, Breadth-First Search, Union Find +5
2646	Minimize the Total Price of the Trips	Tree, Depth-First Search, Graph +2
2681	Power of Heroes	Array, Math, Dynamic Programming +2
2713	Maximum Strictly Increasing Cells in a Matrix	Memoization, Array, Hash Table +5
2719	Count of Integers	Math, String, Dynamic Programming
2742	Painting the Walls	Array, Dynamic Programming
2791	Count Paths That Can Form a Palindrome in a Tree	Bit Manipulation, Tree, Depth-First Search +2
2801	Count Stepping Numbers in Range	String, Dynamic Programming
2809	Minimum Time to Make Array Sum At Most x	Array, Dynamic Programming, Sorting
2827	Number of Beautiful Integers in the Range	Math, Dynamic Programming
2836	Maximize Value of Function in a Ball Passing Game	Bit Manipulation, Array, Dynamic Programming
2851	String Transformation	Math, String, Dynamic Programming +1
2858	Minimum Edge Reversals So Every Node Is Reachable	Depth-First Search, Breadth-First Search, Graph +1
2867	Count Valid Paths in a Tree	Tree, Depth-First Search, Math +2
2876	Count Visited Nodes in a Directed Graph	Graph, Memoization, Dynamic Programming
2902	Count of Sub-Multisets With Bounded Sum	Array, Hash Table, Dynamic Programming +1
2911	Minimum Changes to Make K Semi-palindromes	Two Pointers, String, Dynamic Programming
2912	Number of Ways to Reach Destination in the GridPremium	Math, Dynamic Programming, Combinatorics
2916	Subarrays Distinct Element Sum of Squares II	Binary Indexed Tree, Segment Tree, Array +1
2920	Maximum Points After Collecting Coins From All Nodes	Bit Manipulation, Tree, Depth-First Search +3
2926	Maximum Balanced Subsequence Sum	Binary Indexed Tree, Segment Tree, Array +2
2945	Find Maximum Non-decreasing Array Length	Stack, Queue, Array +4
2969	Minimum Number of Coins for Fruits IIPremium	Queue, Array, Dynamic Programming +2
2973	Find Number of Coins to Place in Tree Nodes	Tree, Depth-First Search, Dynamic Programming +2
2977	Minimum Cost to Convert String II	Graph, Trie, Array +3
2999	Count the Number of Powerful Integers	Math, String, Dynamic Programming

Dynamic Programming pattern FAQ

What is the dynamic programming pattern?

How many LeetCode problems use the dynamic programming pattern?

This page lists 481 LeetCode problems that the dynamic programming pattern applies to: 12 Easy, 243 Medium and 226 Hard. 416 of them carry a complete Python solution with complexity analysis.

What is the time complexity of the dynamic programming pattern?

O(states × transitions) time and O(states), frequently reducible space. The running time is the number of distinct states multiplied by the work done at each one, which is why choosing the state is the whole problem: a one-dimensional state over a prefix gives O(n), a two-dimensional state over two strings gives O(n·m), and a bitmask state over n items gives O(2ⁿ·n). Memoised recursion and a bottom-up table share the same complexity and differ only in constant factors and stack depth. The space often collapses — when row i depends only on row i−1, an O(n·m) table becomes O(m).

When should I use the dynamic programming pattern in an interview?

The problem asks for a count, a maximum, a minimum, or whether something is possible — not for the arrangement itself. A greedy choice is provably wrong because a locally worse choice can lead to a better total.

Which dynamic programming problem should I start with?

LeetCode 70. Climbing Stairs is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.

What patterns are related to dynamic programming?

Backtracking, Greedy, Prefix Sum, Bit Manipulation. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.

More ways in: all 22 patterns, the curated study lists, or the full problem list.

What the dynamic programming pattern is

When to use it

The dynamic programming template in Python

Complexity characteristics

Meet the dynamic programming problem you did not practise.

Approach

Approach

Approach

All 481 dynamic programming LeetCode problems

Easy (12)12

Medium (243)243

Hard (226)226

Related patterns

Dynamic Programming pattern FAQ

What is the dynamic programming pattern?

How many LeetCode problems use the dynamic programming pattern?

What is the time complexity of the dynamic programming pattern?

When should I use the dynamic programming pattern in an interview?

Which dynamic programming problem should I start with?

What patterns are related to dynamic programming?

Easy (12)

Medium (243)

Hard (226)