LeetCode 1092: Shortest Common Supersequence
A clear explanation of finding the shortest string containing both input strings as subsequences using LCS dynamic programming.
Tag
Dynamic-Programming
164 notes
LeetCode 1074: Number of Submatrices That Sum to Target
A clear explanation of counting submatrices with a given sum using 2D prefix sums combined with the subarray sum equals k technique.
LeetCode 1067: Digit Count in Range
A clear explanation of counting the occurrences of a specific digit in all numbers from 1 to n using digit dynamic programming.
LeetCode 1066: Campus Bikes II
A clear explanation of finding the minimum total Manhattan distance to assign bikes to workers using bitmask dynamic programming.
LeetCode 1062: Longest Repeating Substring
A clear explanation of finding the longest substring that appears at least twice using binary search on length with rolling hash.
LeetCode 1049: Last Stone Weight II
A clear explanation of minimizing the last stone weight by splitting stones into two groups using 0/1 knapsack dynamic programming.
LeetCode 1048: Longest String Chain
A clear explanation of finding the longest word chain where each word is formed by inserting one letter into the previous word, using dynamic programming.
LeetCode 1043: Partition Array for Maximum Sum
A clear explanation of maximizing array sum by partitioning into subarrays of at most k elements, each filled with their maximum value, using dynamic programming.
LeetCode 1039: Minimum Score Triangulation of Polygon
A clear explanation of minimizing the total score of triangulating a polygon using interval dynamic programming.
LeetCode 1035: Uncrossed Lines
A clear explanation of maximizing uncrossed connecting lines between two arrays using longest common subsequence dynamic programming.
LeetCode 1031: Maximum Sum of Two Non-Overlapping Subarrays
A clear explanation of finding two non-overlapping subarrays with maximum combined sum using prefix sums and running maximums.
LeetCode 1027: Longest Arithmetic Subsequence
A clear explanation of finding the longest arithmetic subsequence in an array using dynamic programming with difference hash maps.
LeetCode 1025: Divisor Game
A clear explanation of why Alice wins the divisor game if and only if n is even, proven by mathematical induction.
LeetCode 1024: Video Stitching
A clear explanation of finding the minimum number of video clips to cover a time range using a greedy interval covering approach.
LeetCode 1014: Best Sightseeing Pair
A clear explanation of maximizing the sightseeing score by tracking the best left value seen so far in a single pass.
LeetCode 1012: Numbers With Repeated Digits
A clear explanation of counting numbers up to n with at least one repeated digit using digit DP and combinatorics.
LeetCode 964: Least Operators to Express Number
A clear explanation of expressing a target using the fewest operators with repeated uses of x.
LeetCode 940: Distinct Subsequences II
A clear explanation of solving Distinct Subsequences II using dynamic programming and last occurrence tracking.
LeetCode 918: Maximum Sum Circular Subarray
A clear explanation of finding the maximum circular subarray sum using Kadane's algorithm.
LeetCode 740: Delete and Earn
Transform the problem into House Robber dynamic programming by grouping equal values into total points.
LeetCode 549: Binary Tree Longest Consecutive Sequence II
A clear explanation of finding the longest increasing or decreasing consecutive path in a binary tree using DFS.
LeetCode 418: Sentence Screen Fitting
A clear explanation of fitting a sentence onto a screen using cyclic string simulation and greedy row transitions.
LeetCode 413: Arithmetic Slices
A clear explanation of counting arithmetic subarrays using dynamic programming and consecutive differences.
LeetCode 322: Coin Change
A clear explanation of Coin Change using dynamic programming for minimum coin count.
LeetCode 304: Range Sum Query 2D - Immutable
A clear explanation of Range Sum Query 2D - Immutable using a 2D prefix sum matrix for constant-time rectangle queries.
LeetCode 265: Paint House II
A clear explanation of the Paint House II problem using optimized dynamic programming with minimum and second minimum tracking.
LeetCode 174: Dungeon Game
A clear explanation of computing the minimum initial health needed to survive a dungeon using reverse dynamic programming.
LeetCode 120: Triangle
A clear explanation of finding the minimum path sum in a triangle using bottom-up dynamic programming.
LeetCode 119: Pascal's Triangle II
A clear explanation of generating a single row of Pascal's Triangle using in-place dynamic programming.
LeetCode 118: Pascal's Triangle
A clear explanation of generating Pascal's Triangle row by row using dynamic programming.
LeetCode 115: Distinct Subsequences
A clear explanation of counting distinct subsequences using dynamic programming.
LeetCode 64: Minimum Path Sum
A clear guide to finding the minimum path sum in a grid using dynamic programming.
LeetCode 63: Unique Paths II
A clear guide to counting unique paths in a grid with obstacles using dynamic programming.
LeetCode 62: Unique Paths
A clear guide to counting unique paths in a grid using dynamic programming.
LeetCode 975: Odd Even Jump
A clear explanation of counting good starting indices using next-jump preprocessing and dynamic programming.
LeetCode 960: Delete Columns to Make Sorted III
A clear explanation of deleting the minimum number of columns so every remaining row is individually sorted.
LeetCode 956: Tallest Billboard
A clear explanation of solving Tallest Billboard using dynamic programming over height differences.
LeetCode 847: Shortest Path Visiting All Nodes
A clear explanation of the Shortest Path Visiting All Nodes problem using multi-source BFS and bitmask state compression.
LeetCode 838: Push Dominoes
A clear explanation of the Push Dominoes problem using force propagation and a two-pass scan.
LeetCode 837: New 21 Game
A clear explanation of the New 21 Game problem using probability dynamic programming and a sliding window sum.
LeetCode 834: Sum of Distances in Tree
A clear explanation of the Sum of Distances in Tree problem using tree DP, subtree sizes, and rerooting.
LeetCode 828: Count Unique Characters of All Substrings of a Given String
A clear explanation of Count Unique Characters of All Substrings using contribution counting with previous and next occurrences.
LeetCode 920: Number of Music Playlists
A clear explanation of counting valid music playlists using dynamic programming over playlist length and unique songs used.
LeetCode 903: Valid Permutations for DI Sequence
A clear explanation of counting valid DI permutations using dynamic programming and prefix sums.
LeetCode 898: Bitwise ORs of Subarrays
A clear explanation of counting distinct bitwise OR results from all non-empty subarrays using rolling sets.
LeetCode 894: All Possible Full Binary Trees
A clear explanation of generating all full binary trees with n nodes using recursion and memoization.
LeetCode 887: Super Egg Drop
A clear explanation of finding the minimum worst-case number of moves using dynamic programming over eggs and moves.
LeetCode 879: Profitable Schemes
A clear explanation of counting profitable crime schemes using 0/1 knapsack dynamic programming with members and profit states.
LeetCode 877: Stone Game
A clear explanation of the Stone Game problem using game theory and interval dynamic programming.
LeetCode 1000: Minimum Cost to Merge Stones
A clear explanation of merging consecutive stone piles with minimum cost using interval dynamic programming.
LeetCode 983: Minimum Cost For Tickets
A clear explanation of finding the cheapest way to cover all travel days using dynamic programming.
LeetCode 978: Longest Turbulent Subarray
A clear explanation of finding the longest subarray whose adjacent comparisons alternate between greater-than and less-than.
LeetCode 873: Length of Longest Fibonacci Subsequence
A clear explanation of finding the longest Fibonacci-like subsequence using dynamic programming and value-to-index lookup.
LeetCode 943: Find the Shortest Superstring
A clear explanation of solving Find the Shortest Superstring using pairwise overlaps and bitmask dynamic programming.
LeetCode 935: Knight Dialer
A clear explanation of solving Knight Dialer using dynamic programming over the phone keypad graph.
LeetCode 931: Minimum Falling Path Sum
A clear explanation of solving Minimum Falling Path Sum using dynamic programming over matrix rows.
LeetCode 926: Flip String to Monotone Increasing
A clear explanation of solving Flip String to Monotone Increasing with a one-pass dynamic programming approach.
LeetCode 823: Binary Trees With Factors
A dynamic programming solution for counting binary trees where every non-leaf node is the product of its children.
LeetCode 818: Race Car
A dynamic programming solution for finding the shortest instruction sequence that drives a race car to the target position.
LeetCode 813: Largest Sum of Averages
A dynamic programming and prefix sum solution for partitioning an array into adjacent groups with maximum total average.
LeetCode 808: Soup Servings
A probability dynamic programming solution for computing whether soup A empties before soup B, with an early return for large input.
LeetCode 805: Split Array With Same Average
A dynamic programming solution for deciding whether an array can be split into two non-empty groups with the same average.
LeetCode 801: Minimum Swaps To Make Sequences Increasing
A dynamic programming solution for finding the minimum number of same-index swaps needed to make two arrays strictly increasing.
LeetCode 799: Champagne Tower
A clear explanation of simulating overflow in a champagne glass pyramid using dynamic programming.
LeetCode 790: Domino and Tromino Tiling
A clear explanation of counting tilings of a 2 x n board using dominoes and L-shaped trominoes with dynamic programming.
LeetCode 787: Cheapest Flights Within K Stops
A clear explanation of finding the cheapest flight route with at most k stops using bounded Bellman-Ford relaxation.
LeetCode 764: Largest Plus Sign
A clear explanation of finding the largest plus sign in a mined grid using four directional dynamic programming scans.
LeetCode 718: Maximum Length of Repeated Subarray
A clear explanation of finding the longest common contiguous subarray using dynamic programming.
LeetCode 714: Best Time to Buy and Sell Stock with Transaction Fee
A clear explanation of maximizing stock trading profit with unlimited transactions and a fixed transaction fee using dynamic programming.
LeetCode 712: Minimum ASCII Delete Sum for Two Strings
A clear explanation of using dynamic programming to minimize the ASCII cost of deletions needed to make two strings equal.
LeetCode 746: Min Cost Climbing Stairs
Find the minimum cost to reach the top of the staircase using dynamic programming.
LeetCode 741: Cherry Pickup
Maximize cherries collected on a round trip by converting the problem into two simultaneous forward paths and solving with dynamic programming.
LeetCode 730: Count Different Palindromic Subsequences
Count distinct non-empty palindromic subsequences using interval dynamic programming and duplicate handling.
LeetCode 727: Minimum Window Subsequence
Find the shortest substring of s1 that contains s2 as a subsequence using dynamic programming.
LeetCode 698: Partition to K Equal Sum Subsets
Decide whether an array can be divided into k non-empty subsets with equal sums using backtracking and pruning.
LeetCode 691: Stickers to Spell Word
Find the minimum number of stickers needed to form a target string using top-down dynamic programming with memoization.
LeetCode 689: Maximum Sum of 3 Non-Overlapping Subarrays
Find three non-overlapping subarrays of length k with maximum total sum and return the lexicographically smallest starting indices.
LeetCode 688: Knight Probability in Chessboard
Compute the probability that a knight remains on an n x n chessboard after exactly k random moves using dynamic programming.
LeetCode 674: Longest Continuous Increasing Subsequence
A clear explanation of finding the longest strictly increasing contiguous subarray using a single scan.
LeetCode 673: Number of Longest Increasing Subsequence
A clear explanation of counting how many longest strictly increasing subsequences exist using dynamic programming.
LeetCode 664: Strange Printer
A clear explanation of minimizing printer turns using interval dynamic programming.
LeetCode 656: Coin Path
A clear explanation of finding the minimum-cost path with bounded jumps, blocked cells, and lexicographic tie-breaking.
LeetCode 651: 4 Keys Keyboard
A dynamic programming solution for maximizing the number of A characters printed with a limited number of keyboard operations.
LeetCode 650: 2 Keys Keyboard
A dynamic programming and prime factorization solution for finding the minimum operations needed to produce n characters.
LeetCode 646: Maximum Length of Pair Chain
A greedy interval scheduling solution for finding the longest chain of valid pairs.
LeetCode 639: Decode Ways II
A dynamic programming solution for counting decodings of a digit string with wildcard characters.
LeetCode 638: Shopping Offers
A DFS and memoization solution for finding the minimum cost to satisfy item needs using individual prices and reusable special offers.
LeetCode 634: Find the Derangement of An Array
A dynamic programming and combinatorics solution for counting permutations with no fixed positions.
LeetCode 629: K Inverse Pairs Array
A dynamic programming solution for counting permutations of 1 to n with exactly k inverse pairs.
LeetCode 45: Jump Game II
A clear explanation of Jump Game II using a greedy range expansion approach to find the minimum number of jumps.
LeetCode 44: Wildcard Matching
A clear explanation of Wildcard Matching using dynamic programming over string and pattern prefixes.
LeetCode 42: Trapping Rain Water
A clear explanation of the Trapping Rain Water problem using left and right boundaries, then an optimized two-pointer solution.
LeetCode 600: Non-negative Integers without Consecutive Ones
A clear digit dynamic programming solution for counting numbers whose binary representation does not contain consecutive ones.
LeetCode 583: Delete Operation for Two Strings
A clear dynamic programming solution for finding the minimum deletions needed to make two strings equal.
LeetCode 576: Out of Boundary Paths
A clear dynamic programming solution for counting paths that move a ball out of a grid boundary.
LeetCode 568: Maximum Vacation Days
A clear explanation of Maximum Vacation Days using dynamic programming over weeks and cities.
LeetCode 562: Longest Line of Consecutive One in Matrix
A clear explanation of Longest Line of Consecutive One in Matrix using dynamic programming over four directions.
LeetCode 552: Student Attendance Record II
A clear explanation of Student Attendance Record II using dynamic programming over absence count and late streak.
LeetCode 546: Remove Boxes
A clear explanation of maximizing remove-box scores using interval dynamic programming with memoization.
LeetCode 542: 01 Matrix
A clear explanation of computing the distance to the nearest zero in a binary matrix using multi-source BFS.
LeetCode 526: Beautiful Arrangement
A clear explanation of counting beautiful arrangements using backtracking and divisibility pruning.
LeetCode 518: Coin Change II
A clear explanation of counting coin-change combinations using dynamic programming.
LeetCode 514: Freedom Trail
A clear explanation of finding the minimum steps to spell a key on a circular ring using dynamic programming and memoized DFS.
LeetCode 516: Longest Palindromic Subsequence
A clear explanation of finding the length of the longest palindromic subsequence using interval dynamic programming.
LeetCode 509: Fibonacci Number
A clear explanation of computing Fibonacci numbers using dynamic programming and iterative state transitions.
LeetCode 494: Target Sum
A clear explanation of counting sign assignments that reach a target using recursion first, then subset-sum dynamic programming.
LeetCode 486: Predict the Winner
A clear explanation of predicting whether Player 1 can win using minimax dynamic programming over score difference.
LeetCode 474: Ones and Zeroes
A clear explanation of solving the largest subset problem as a two-dimensional 0/1 knapsack over zero and one counts.
LeetCode 472: Concatenated Words
A clear explanation of finding all words that can be formed by concatenating at least two shorter words from the same list.
LeetCode 471: Encode String with Shortest Length
A clear explanation of interval dynamic programming for encoding a string into the shortest k[encoded_string] form.
LeetCode 467: Unique Substrings in Wraparound String
A clear explanation of counting unique substrings that appear in the infinite alphabet wraparound string using dynamic programming by ending character.
LeetCode 466: Count The Repetitions
A clear explanation of counting how many repeated copies of one string can be obtained as a subsequence of another repeated string.
LeetCode 464: Can I Win
A clear explanation of solving the Can I Win game using minimax recursion, bitmask state compression, and memoization.
LeetCode 446: Arithmetic Slices II - Subsequence
Count arithmetic subsequences of length at least three using dynamic programming with one hash map per ending index.
LeetCode 416: Partition Equal Subset Sum
A clear explanation of deciding whether an array can be split into two equal-sum subsets using 0/1 knapsack dynamic programming.
LeetCode 403: Frog Jump
A clear explanation of the Frog Jump problem using dynamic programming with reachable jump sizes.
LeetCode 410: Split Array Largest Sum
A clear explanation of minimizing the largest subarray sum using binary search on the answer and greedy validation.
LeetCode 396: Rotate Function
A clear explanation of maximizing the rotation function using a recurrence instead of simulating every rotation.
LeetCode 392: Is Subsequence
A clear explanation of checking whether one string is a subsequence of another using two pointers.
LeetCode 377: Combination Sum IV
A clear explanation of Combination Sum IV using dynamic programming to count ordered combinations that sum to a target.
LeetCode 376: Wiggle Subsequence
A clear explanation of the Wiggle Subsequence problem using dynamic programming intuition and an optimized greedy solution.
LeetCode 375: Guess Number Higher or Lower II
A clear explanation of finding the minimum guaranteed cost using interval dynamic programming.
LeetCode 368: Largest Divisible Subset
A clear explanation of finding the largest subset where every pair is divisible using sorting, dynamic programming, and parent reconstruction.
LeetCode 361: Bomb Enemy
A clear explanation of finding the best bomb placement in a grid using cached row and column segment counts.
LeetCode 357: Count Numbers with Unique Digits
A clear explanation of counting numbers with unique digits using combinatorics.
LeetCode 354: Russian Doll Envelopes
A clear explanation of solving Russian Doll Envelopes using sorting and longest increasing subsequence.
LeetCode 343: Integer Break
A clear explanation of Integer Break using dynamic programming, with a note on the greedy math solution.
LeetCode 338: Counting Bits
A clear explanation of Counting Bits using dynamic programming and bit manipulation.
LeetCode 337: House Robber III
A clear explanation of House Robber III using tree dynamic programming with rob and skip states.
LeetCode 329: Longest Increasing Path in a Matrix
A clear explanation of Longest Increasing Path in a Matrix using DFS with memoization.
LeetCode 313: Super Ugly Number
A clear explanation of Super Ugly Number using dynamic programming with one pointer per prime.
LeetCode 312: Burst Balloons
A clear explanation of Burst Balloons using interval dynamic programming and the last-burst idea.
LeetCode 309: Best Time to Buy and Sell Stock with Cooldown
A clear explanation of Best Time to Buy and Sell Stock with Cooldown using dynamic programming states.
LeetCode 300: Longest Increasing Subsequence
A dynamic programming and patience sorting solution for finding the longest strictly increasing subsequence in an array.
LeetCode 279: Perfect Squares
A dynamic programming solution for finding the least number of perfect square numbers that sum to n.
LeetCode 276: Paint Fence
A dynamic programming solution for counting ways to paint fence posts with no more than two adjacent posts sharing the same color.
LeetCode 264: Ugly Number II
A clear explanation of the Ugly Number II problem using dynamic programming with three pointers.
LeetCode 256: Paint House
A clear explanation of the Paint House problem using dynamic programming with constant space.
LeetCode 221: Maximal Square
A clear explanation of finding the largest square of 1s in a binary matrix using dynamic programming.
LeetCode 213: House Robber II
A clear explanation of maximizing robbed money from circularly arranged houses using dynamic programming.
LeetCode 97: Interleaving String
A detailed guide to solving Interleaving String with two-dimensional dynamic programming.
LeetCode 96: Unique Binary Search Trees
A detailed guide to solving Unique Binary Search Trees with dynamic programming and the Catalan recurrence.
LeetCode 95: Unique Binary Search Trees II
A detailed guide to solving Unique Binary Search Trees II with recursive tree generation over value ranges.
LeetCode 91: Decode Ways
A detailed guide to solving Decode Ways with dynamic programming and careful handling of zeroes.
LeetCode 87: Scramble String
A detailed guide to solving Scramble String with recursive dynamic programming and memoization.
LeetCode 85: Maximal Rectangle
A detailed guide to solving Maximal Rectangle by converting each matrix row into a histogram and applying a monotonic stack.
LeetCode 198: House Robber
A clear explanation of maximizing robbery profit without robbing adjacent houses using dynamic programming.
LeetCode 188: Best Time to Buy and Sell Stock IV
A clear explanation of maximizing stock trading profit with at most k transactions using dynamic programming.
LeetCode 152: Maximum Product Subarray
A detailed explanation of tracking both maximum and minimum products while scanning the array.
LeetCode 140: Word Break II
Return all valid sentences formed by inserting spaces into a string so every word belongs to the dictionary, using DFS with memoization.
LeetCode 139: Word Break
Decide whether a string can be segmented into dictionary words using dynamic programming over prefixes.
LeetCode 132: Palindrome Partitioning II
Find the minimum number of cuts needed to split a string into palindromic substrings using palindrome precomputation and dynamic programming.
LeetCode 131: Palindrome Partitioning
Generate all ways to split a string so that every piece is a palindrome, using backtracking with palindrome precomputation.
LeetCode 124: Binary Tree Maximum Path Sum
A clear explanation of finding the maximum path sum in a binary tree using bottom-up depth-first search.
LeetCode 123: Best Time to Buy and Sell Stock III
A clear explanation of maximizing stock profit with at most two transactions using dynamic programming.
LeetCode 122: Best Time to Buy and Sell Stock II
A clear explanation of maximizing stock profit with unlimited transactions using a greedy single-pass method.
LeetCode 121: Best Time to Buy and Sell Stock
A clear explanation of finding the maximum profit from one stock transaction using a single pass.
LeetCode 72: Edit Distance
A clear guide to computing the minimum number of insert, delete, and replace operations needed to convert one string into another.
LeetCode 70: Climbing Stairs
A clear guide to counting distinct ways to climb stairs using dynamic programming.
LeetCode 55: Jump Game
A clear guide to solving Jump Game with greedy reachability.
LeetCode 53: Maximum Subarray
A clear guide to solving Maximum Subarray with brute force first, then Kadane's dynamic programming algorithm.
LeetCode 32: Longest Valid Parentheses
A clear explanation of finding the longest well-formed parentheses substring using a stack of indices.
LeetCode 10: Regular Expression Matching
A detailed explanation of matching a full string against a simplified regular expression with dot and star using dynamic programming.
1.15 Dynamic Programming
Dynamic programming solves problems by storing answers to subproblems and reusing them.