Dynamic Programming LeetCode Problems: All 481,
With Python Solutions

Every problem in this library that LeetCode tags Dynamic Programming. 416 of them carry a complete Python solution, a worked example and the time and space complexity of the approach.

Get Stealth Interview

Easy: 12
Medium: 243
Hard: 226

1 pattern

How Dynamic Programming problems are solved

A tag names the subject, not the method. These pattern hubs cover the techniques that actually solve Dynamic Programming problems — each one explains the approach, gives a Python template and states its complexity.

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

Eyes only

When the Dynamic Programming problem arrives live.

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+

Dynamic Programming problems by difficulty

Showing the first 200 of 481 problems. Problems with a complete Python solution are listed first, then by ascending problem number.

Easy (10)

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
1025	Divisor Game	Brainteaser, Math, Dynamic Programming +1
1137	N-th Tribonacci Number	Memoization, Math, Dynamic Programming

Medium (111)

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
0764	Largest Plus Sign	Array, Dynamic Programming
0787	Cheapest Flights Within K Stops	Depth-First Search, Breadth-First Search, Graph +3
0788	Rotated Digits	Math, Dynamic Programming
0790	Domino and Tromino Tiling	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
0918	Maximum Sum Circular Subarray	Queue, Array, Divide and Conquer +2
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
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
1143	Longest Common Subsequence	String, Dynamic Programming
1155	Number of Dice Rolls With Target Sum	Dynamic Programming
1162	As Far from Land as Possible	Breadth-First Search, Array, Dynamic Programming +1
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
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

Hard (79)

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
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
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
1220	Count Vowels Permutation	Dynamic Programming
1223	Dice Roll Simulation	Array, Dynamic Programming
1235	Maximum Profit in Job Scheduling	Array, Binary Search, Dynamic Programming +1
1255	Maximum Score Words Formed by Letters	Bit Manipulation, Array, Hash Table +5
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

How Dynamic Programming problems are solved

When the Dynamic Programming problem arrives live.

Approach

Approach

Approach

Dynamic Programming problems by difficulty

Easy (10)10

Medium (111)111

Hard (79)79

Keep exploring

Easy (10)

Medium (111)

Hard (79)