← back

Dynamic Programming

568 questions · 0 seen

All Dynamic Programming problems

Problems

5 Longest Palindromic Substring
10 Regular Expression Matching
22 Generate Parentheses
32 Longest Valid Parentheses
42 Trapping Rain Water
44 Wildcard Matching
45 Jump Game II
53 Maximum Subarray
55 Jump Game
62 Unique Paths
63 Unique Paths II
64 Minimum Path Sum
70 Climbing Stairs
72 Edit Distance
85 Maximal Rectangle
87 Scramble String
91 Decode Ways
95 Unique Binary Search Trees II
96 Unique Binary Search Trees
97 Interleaving String
115 Distinct Subsequences
118 Pascal's Triangle
119 Pascal's Triangle II
120 Triangle
121 Best Time to Buy and Sell Stock
122 Best Time to Buy and Sell Stock II
123 Best Time to Buy and Sell Stock III
124 Binary Tree Maximum Path Sum
131 Palindrome Partitioning
132 Palindrome Partitioning II
139 Word Break
140 Word Break II
152 Maximum Product Subarray
174 Dungeon Game
188 Best Time to Buy and Sell Stock IV
198 House Robber
213 House Robber II
221 Maximal Square
233 Number of Digit One
241 Different Ways to Add Parentheses
264 Ugly Number II
279 Perfect Squares
300 Longest Increasing Subsequence
309 Best Time to Buy and Sell Stock with Cooldown
312 Burst Balloons
313 Super Ugly Number
322 Coin Change
329 Longest Increasing Path in a Matrix
337 House Robber III
338 Counting Bits
343 Integer Break
354 Russian Doll Envelopes
357 Count Numbers with Unique Digits
368 Largest Divisible Subset
375 Guess Number Higher or Lower II
376 Wiggle Subsequence
377 Combination Sum IV
392 Is Subsequence
396 Rotate Function
397 Integer Replacement
403 Frog Jump
410 Split Array Largest Sum
413 Arithmetic Slices
416 Partition Equal Subset Sum
435 Non-overlapping Intervals
446 Arithmetic Slices II - Subsequence
458 Poor Pigs
464 Can I Win
466 Count The Repetitions
467 Unique Substrings in Wraparound String
472 Concatenated Words
473 Matchsticks to Square
474 Ones and Zeroes
486 Predict the Winner
488 Zuma Game
494 Target Sum
509 Fibonacci Number
514 Freedom Trail
516 Longest Palindromic Subsequence
518 Coin Change II
526 Beautiful Arrangement
542 01 Matrix
546 Remove Boxes
552 Student Attendance Record II
553 Optimal Division
576 Out of Boundary Paths
583 Delete Operation for Two Strings
600 Non-negative Integers without Consecutive Ones
629 K Inverse Pairs Array
638 Shopping Offers
639 Decode Ways II
646 Maximum Length of Pair Chain
647 Palindromic Substrings
650 2 Keys Keyboard
664 Strange Printer
673 Number of Longest Increasing Subsequence
678 Valid Parenthesis String
688 Knight Probability in Chessboard
689 Maximum Sum of 3 Non-Overlapping Subarrays
691 Stickers to Spell Word
698 Partition to K Equal Sum Subsets
712 Minimum ASCII Delete Sum for Two Strings
714 Best Time to Buy and Sell Stock with Transaction Fee
718 Maximum Length of Repeated Subarray
730 Count Different Palindromic Subsequences
740 Delete and Earn
741 Cherry Pickup
746 Min Cost Climbing Stairs
764 Largest Plus Sign
773 Sliding Puzzle
787 Cheapest Flights Within K Stops
788 Rotated Digits
790 Domino and Tromino Tiling
792 Number of Matching Subsequences
799 Champagne Tower
801 Minimum Swaps To Make Sequences Increasing
805 Split Array With Same Average
808 Soup Servings
813 Largest Sum of Averages
818 Race Car
823 Binary Trees With Factors
828 Count Unique Characters of All Substrings of a Given String
834 Sum of Distances in Tree
837 New 21 Game
838 Push Dominoes
845 Longest Mountain in Array
847 Shortest Path Visiting All Nodes
871 Minimum Number of Refueling Stops
873 Length of Longest Fibonacci Subsequence
877 Stone Game
879 Profitable Schemes
887 Super Egg Drop
894 All Possible Full Binary Trees
898 Bitwise ORs of Subarrays
902 Numbers At Most N Given Digit Set
903 Valid Permutations for DI Sequence
907 Sum of Subarray Minimums
913 Cat and Mouse
918 Maximum Sum Circular Subarray
920 Number of Music Playlists
926 Flip String to Monotone Increasing
931 Minimum Falling Path Sum
935 Knight Dialer
940 Distinct Subsequences II
943 Find the Shortest Superstring
956 Tallest Billboard
960 Delete Columns to Make Sorted III
964 Least Operators to Express Number
968 Binary Tree Cameras
975 Odd Even Jump
978 Longest Turbulent Subarray
983 Minimum Cost For Tickets
996 Number of Squareful Arrays
1000 Minimum Cost to Merge Stones
1012 Numbers With Repeated Digits
1014 Best Sightseeing Pair
1024 Video Stitching
1025 Divisor Game
1027 Longest Arithmetic Subsequence
1031 Maximum Sum of Two Non-Overlapping Subarrays
1035 Uncrossed Lines
1039 Minimum Score Triangulation of Polygon
1043 Partition Array for Maximum Sum
1048 Longest String Chain
1049 Last Stone Weight II
1092 Shortest Common Supersequence
1105 Filling Bookcase Shelves
1125 Smallest Sufficient Team
1130 Minimum Cost Tree From Leaf Values
1137 N-th Tribonacci Number
1139 Largest 1-Bordered Square
1140 Stone Game II
1143 Longest Common Subsequence
1147 Longest Chunked Palindrome Decomposition
1155 Number of Dice Rolls With Target Sum
1162 As Far from Land as Possible
1186 Maximum Subarray Sum with One Deletion
1187 Make Array Strictly Increasing
1191 K-Concatenation Maximum Sum
1218 Longest Arithmetic Subsequence of Given Difference
1220 Count Vowels Permutation
1223 Dice Roll Simulation
1227 Airplane Seat Assignment Probability
1235 Maximum Profit in Job Scheduling
1255 Maximum Score Words Formed by Letters
1262 Greatest Sum Divisible by Three
1269 Number of Ways to Stay in the Same Place After Some Steps
1277 Count Square Submatrices with All Ones
1278 Palindrome Partitioning III
1289 Minimum Falling Path Sum II
1301 Number of Paths with Max Score
1312 Minimum Insertion Steps to Make a String Palindrome
1320 Minimum Distance to Type a Word Using Two Fingers
1326 Minimum Number of Taps to Open to Water a Garden
1334 Find the City With the Smallest Number of Neighbors at a Threshold Distance
1335 Minimum Difficulty of a Job Schedule
1340 Jump Game V
1349 Maximum Students Taking Exam
1359 Count All Valid Pickup and Delivery Options
1363 Largest Multiple of Three
1372 Longest ZigZag Path in a Binary Tree
1373 Maximum Sum BST in Binary Tree
1387 Sort Integers by The Power Value
1388 Pizza With 3n Slices
1395 Count Number of Teams
1397 Find All Good Strings
1402 Reducing Dishes
1406 Stone Game III
1411 Number of Ways to Paint N × 3 Grid
1416 Restore The Array
1420 Build Array Where You Can Find The Maximum Exactly K Comparisons
1425 Constrained Subsequence Sum
1434 Number of Ways to Wear Different Hats to Each Other
1444 Number of Ways of Cutting a Pizza
1449 Form Largest Integer With Digits That Add up to Target
1458 Max Dot Product of Two Subsequences
1463 Cherry Pickup II
1467 Probability of a Two Boxes Having The Same Number of Distinct Balls
1473 Paint House III
1477 Find Two Non-overlapping Sub-arrays Each With Target Sum
1478 Allocate Mailboxes
1483 Kth Ancestor of a Tree Node
1493 Longest Subarray of 1's After Deleting One Element
1494 Parallel Courses II
1504 Count Submatrices With All Ones
1510 Stone Game IV
1524 Number of Sub-arrays With Odd Sum
1525 Number of Good Ways to Split a String
1526 Minimum Number of Increments on Subarrays to Form a Target Array
1531 String Compression II
1537 Get the Maximum Score
1547 Minimum Cost to Cut a Stick
1553 Minimum Number of Days to Eat N Oranges
1563 Stone Game V
1567 Maximum Length of Subarray With Positive Product
1569 Number of Ways to Reorder Array to Get Same BST
1575 Count All Possible Routes
1578 Minimum Time to Make Rope Colorful
1594 Maximum Non Negative Product in a Matrix
1595 Minimum Cost to Connect Two Groups of Points
1611 Minimum One Bit Operations to Make Integers Zero
1617 Count Subtrees With Max Distance Between Cities
1621 Number of Sets of K Non-Overlapping Line Segments
1626 Best Team With No Conflicts
1638 Count Substrings That Differ by One Character (PRO)
1639 Number of Ways to Form a Target String Given a Dictionary
1641 Count Sorted Vowel Strings
1643 Kth Smallest Instructions
1653 Minimum Deletions to Make String Balanced
1655 Distribute Repeating Integers
1659 Maximize Grid Happiness
1668 Maximum Repeating Substring (PRO)
1671 Minimum Number of Removals to Make Mountain Array
1681 Minimum Incompatibility
1687 Delivering Boxes from Storage to Ports
1690 Stone Game VII
1691 Maximum Height by Stacking Cuboids
1696 Jump Game VI
1723 Find Minimum Time to Finish All Jobs
1728 Cat and Mouse II
1735 Count Ways to Make Array With Product
1745 Palindrome Partitioning IV
1749 Maximum Absolute Sum of Any Subarray
1751 Maximum Number of Events That Can Be Attended II
1755 Closest Subsequence Sum
1770 Maximum Score from Performing Multiplication Operations
1771 Maximize Palindrome Length From Subsequences
1774 Closest Dessert Cost
1786 Number of Restricted Paths From First to Last Node
1787 Make the XOR of All Segments Equal to Zero
1799 Maximize Score After N Operations
1815 Maximum Number of Groups Getting Fresh Donuts
1824 Minimum Sideway Jumps
1857 Largest Color Value in a Directed Graph
1866 Number of Ways to Rearrange Sticks With K Sticks Visible
1871 Jump Game VII
1872 Stone Game VIII
1879 Minimum XOR Sum of Two Arrays
1883 Minimum Skips to Arrive at Meeting On Time
1884 Egg Drop With 2 Eggs and N Floors
1888 Minimum Number of Flips to Make the Binary String Alternating
1896 Minimum Cost to Change the Final Value of Expression
1900 The Earliest and Latest Rounds Where Players Compete
1911 Maximum Alternating Subsequence Sum
1916 Count Ways to Build Rooms in an Ant Colony
1928 Minimum Cost to Reach Destination in Time
1931 Painting a Grid With Three Different Colors
1937 Maximum Number of Points with Cost
1947 Maximum Compatibility Score Sum
1955 Count Number of Special Subsequences
1959 Minimum Total Space Wasted With K Resizing Operations
1976 Number of Ways to Arrive at Destination
1977 Number of Ways to Separate Numbers
1981 Minimize the Difference Between Target and Chosen Elements
1986 Minimum Number of Work Sessions to Finish the Tasks
1987 Number of Unique Good Subsequences
1994 The Number of Good Subsets
1997 First Day Where You Have Been in All the Rooms
2002 Maximum Product of the Length of Two Palindromic Subsequences
2003 Smallest Missing Genetic Value in Each Subtree
2008 Maximum Earnings From Taxi
2019 The Score of Students Solving Math Expression
2035 Partition Array Into Two Arrays to Minimize Sum Difference
2050 Parallel Courses III
2054 Two Best Non-Overlapping Events
2060 Check if an Original String Exists Given Two Encoded Strings
2063 Vowels of All Substrings
2086 Minimum Number of Food Buckets to Feed the Hamsters
2088 Count Fertile Pyramids in a Land
2100 Find Good Days to Rob the Bank
2110 Number of Smooth Descent Periods of a Stock
2127 Maximum Employees to Be Invited to a Meeting
2140 Solving Questions With Brainpower
2147 Number of Ways to Divide a Long Corridor
2163 Minimum Difference in Sums After Removal of Elements
2167 Minimum Time to Remove All Cars Containing Illegal Goods
2172 Maximum AND Sum of Array
2188 Minimum Time to Finish the Race
2209 Minimum White Tiles After Covering With Carpets
2218 Maximum Value of K Coins From Piles
2222 Number of Ways to Select Buildings
2262 Total Appeal of A String
2266 Count Number of Texts
2267 Check if There Is a Valid Parentheses String Path
2272 Substring With Largest Variance
2289 Steps to Make Array Non-decreasing
2304 Minimum Path Cost in a Grid
2305 Fair Distribution of Cookies
2310 Sum of Numbers With Units Digit K
2311 Longest Binary Subsequence Less Than or Equal to K
2312 Selling Pieces of Wood
2318 Number of Distinct Roll Sequences
2320 Count Number of Ways to Place Houses
2321 Maximum Score Of Spliced Array
2327 Number of People Aware of a Secret
2328 Number of Increasing Paths in a Grid
2338 Count the Number of Ideal Arrays
2369 Check if There is a Valid Partition For The Array
2370 Longest Ideal Subsequence
2376 Count Special Integers
2380 Time Needed to Rearrange a Binary String
2400 Number of Ways to Reach a Position After Exactly k Steps
2407 Longest Increasing Subsequence II
2420 Find All Good Indices
2430 Maximum Deletions on a String
2435 Paths in Matrix Whose Sum Is Divisible by K
2439 Minimize Maximum of Array
2463 Minimum Total Distance Traveled
2466 Count Ways To Build Good Strings
2472 Maximum Number of Non-overlapping Palindrome Substrings
2478 Number of Beautiful Partitions
2484 Count Palindromic Subsequences
2501 Longest Square Streak in an Array
2518 Number of Great Partitions
2522 Partition String Into Substrings With Values at Most K
2538 Difference Between Maximum and Minimum Price Sum
2547 Minimum Cost to Split an Array
2552 Count Increasing Quadruplets
2556 Disconnect Path in a Binary Matrix by at Most One Flip
2560 House Robber IV
2571 Minimum Operations to Reduce an Integer to 0
2572 Count the Number of Square-Free Subsets
2573 Find the String with LCP
2581 Count Number of Possible Root Nodes
2585 Number of Ways to Earn Points
2597 The Number of Beautiful Subsets
2606 Find the Substring With Maximum Cost
2616 Minimize the Maximum Difference of Pairs
2617 Minimum Number of Visited Cells in a Grid
2645 Minimum Additions to Make Valid String
2646 Minimize the Total Price of the Trips
2673 Make Costs of Paths Equal in a Binary Tree
2681 Power of Heroes
2684 Maximum Number of Moves in a Grid
2707 Extra Characters in a String
2708 Maximum Strength of a Group
2712 Minimum Cost to Make All Characters Equal
2713 Maximum Strictly Increasing Cells in a Matrix
2719 Count of Integers
2741 Special Permutations
2742 Painting the Walls
2745 Construct the Longest New String
2746 Decremental String Concatenation
2750 Ways to Split Array Into Good Subarrays
2767 Partition String Into Minimum Beautiful Substrings
2770 Maximum Number of Jumps to Reach the Last Index
2771 Longest Non-decreasing Subarray From Two Arrays
2786 Visit Array Positions to Maximize Score
2787 Ways to Express an Integer as Sum of Powers
2791 Count Paths That Can Form a Palindrome in a Tree
2801 Count Stepping Numbers in Range
2809 Minimum Time to Make Array Sum At Most x
2811 Check if it is Possible to Split Array
2826 Sorting Three Groups
2827 Number of Beautiful Integers in the Range
2830 Maximize the Profit as the Salesman
2836 Maximize Value of Function in a Ball Passing Game
2850 Minimum Moves to Spread Stones Over Grid
2851 String Transformation
2858 Minimum Edge Reversals So Every Node Is Reachable
2867 Count Valid Paths in a Tree
2876 Count Visited Nodes in a Directed Graph
2896 Apply Operations to Make Two Strings Equal
2900 Longest Unequal Adjacent Groups Subsequence I
2901 Longest Unequal Adjacent Groups Subsequence II
2902 Count of Sub-Multisets With Bounded Sum
2911 Minimum Changes to Make K Semi-palindromes
2915 Length of the Longest Subsequence That Sums to Target
2916 Subarrays Distinct Element Sum of Squares II
2919 Minimum Increment Operations to Make Array Beautiful
2920 Maximum Points After Collecting Coins From All Nodes
2925 Maximum Score After Applying Operations on a Tree
2926 Maximum Balanced Subsequence Sum
2930 Number of Strings Which Can Be Rearranged to Contain Substring
2944 Minimum Number of Coins for Fruits
2945 Find Maximum Non-decreasing Array Length
2957 Remove Adjacent Almost-Equal Characters
2973 Find Number of Coins to Place in Tree Nodes
2977 Minimum Cost to Convert String II
2998 Minimum Number of Operations to Make X and Y Equal
2999 Count the Number of Powerful Integers
3003 Maximize the Number of Partitions After Operations
3007 Maximum Number That Sum of the Prices Is Less Than or Equal to K
3040 Maximum Number of Operations With the Same Score II
3041 Maximize Consecutive Elements in an Array After Modification
3068 Find the Maximum Sum of Node Values
3077 Maximum Strength of K Disjoint Subarrays
3082 Find the Sum of the Power of All Subsequences
3098 Find the Sum of Subsequence Powers
3117 Minimum Sum of Values by Dividing Array
3122 Minimum Number of Operations to Satisfy Conditions
3129 Find All Possible Stable Binary Arrays I
3130 Find All Possible Stable Binary Arrays II
3144 Minimum Substring Partition of Equal Character Frequency
3147 Taking Maximum Energy From the Mystic Dungeon
3148 Maximum Difference Score in a Grid
3149 Find the Minimum Cost Array Permutation
3154 Find Number of Ways to Reach the K-th Stair
3165 Maximum Sum of Subsequence With Non-adjacent Elements
3176 Find the Maximum Length of a Good Subsequence I
3177 Find the Maximum Length of a Good Subsequence II
3180 Maximum Total Reward Using Operations I
3181 Maximum Total Reward Using Operations II
3186 Maximum Total Damage With Spell Casting
3192 Minimum Operations to Make Binary Array Elements Equal to One II
3193 Count the Number of Inversions
3196 Maximize Total Cost of Alternating Subarrays
3201 Find the Maximum Length of Valid Subsequence I
3202 Find the Maximum Length of Valid Subsequence II
3213 Construct String with Minimum Cost
3218 Minimum Cost for Cutting Cake I
3225 Maximum Score From Grid Operations
3229 Minimum Operations to Make Array Equal to Target
3241 Time Taken to Mark All Nodes
3250 Find the Count of Monotonic Pairs I
3251 Find the Count of Monotonic Pairs II
3256 Maximum Value Sum by Placing Three Rooks I
3257 Maximum Value Sum by Placing Three Rooks II
3259 Maximum Energy Boost From Two Drinks
3260 Find the Largest Palindrome Divisible by K
3276 Select Cells in Grid With Maximum Score
3277 Maximum XOR Score Subarray Queries
3287 Find the Maximum Sequence Value of Array
3290 Maximum Multiplication Score
3291 Minimum Number of Valid Strings to Form Target I
3292 Minimum Number of Valid Strings to Form Target II
3302 Find the Lexicographically Smallest Valid Sequence
3316 Find Maximum Removals From Source String
3317 Find the Number of Possible Ways for an Event
3320 Count The Number of Winning Sequences
3332 Maximum Points Tourist Can Earn
3333 Find the Original Typed String II
3335 Total Characters in String After Transformations I
3336 Find the Number of Subsequences With Equal GCD
3337 Total Characters in String After Transformations II
3343 Count Number of Balanced Permutations
3351 Sum of Good Subsequences
3352 Count K-Reducible Numbers Less Than N
3363 Find the Maximum Number of Fruits Collected
3366 Minimum Array Sum
3367 Maximize Sum of Weights after Edge Removals
3376 Minimum Time to Break Locks I
3388 Count Beautiful Splits in an Array
3389 Minimum Operations to Make Character Frequencies Equal
3393 Count Paths With the Given XOR Value
3409 Longest Subsequence With Decreasing Adjacent Difference
3410 Maximize Subarray Sum After Removing All Occurrences of One Element
3414 Maximum Score of Non-overlapping Intervals
3418 Maximum Amount of Money Robot Can Earn
3428 Maximum and Minimum Sums of at Most Size K Subsequences
3429 Paint House IV
3434 Maximum Frequency After Subarray Operation
3441 Minimum Cost Good Caption
3444 Minimum Increments for Target Multiples in an Array
3448 Count Substrings Divisible By Last Digit
3458 Select K Disjoint Special Substrings
3459 Length of Longest V-Shaped Diagonal Segment
3469 Find Minimum Cost to Remove Array Elements
3472 Longest Palindromic Subsequence After at Most K Operations
3473 Sum of K Subarrays With Length at Least M
3489 Zero Array Transformation IV
3490 Count Beautiful Numbers
3500 Minimum Cost to Divide Array Into Subarrays
3503 Longest Palindrome After Substring Concatenation I
3504 Longest Palindrome After Substring Concatenation II
3505 Minimum Operations to Make Elements Within K Subarrays Equal
3509 Maximum Product of Subsequences With an Alternating Sum Equal to K
3519 Count Numbers with Non-Decreasing Digits
3524 Find X Value of Array I
3530 Maximum Profit from Valid Topological Order in DAG
3533 Concatenated Divisibility
3534 Path Existence Queries in a Graph II
3538 Merge Operations for Minimum Travel Time
3539 Find Sum of Array Product of Magical Sequences
3543 Maximum Weighted K-Edge Path
3544 Subtree Inversion Sum
3553 Minimum Weighted Subgraph With the Required Paths II
3557 Find Maximum Number of Non Intersecting Substrings
3559 Number of Ways to Assign Edge Weights II
3562 Maximum Profit from Trading Stocks with Discounts
3563 Lexicographically Smallest String After Adjacent Removals
3573 Best Time to Buy and Sell Stock V
3575 Maximum Good Subtree Score
3578 Count Partitions With Max-Min Difference at Most K
3579 Minimum Steps to Convert String with Operations
3585 Find Weighted Median Node in Tree
3592 Inverse Coin Change
3593 Minimum Increments to Equalize Leaf Paths
3594 Minimum Time to Transport All Individuals
3599 Partition Array to Minimize XOR
3603 Minimum Cost Path with Alternating Directions II
3615 Longest Palindromic Path in Graph
3620 Network Recovery Pathways
3621 Number of Integers With Popcount-Depth Equal to K I
3628 Maximum Number of Subsequences After One Inserting
3638 Maximum Balanced Shipments
3640 Trionic Array II
3651 Minimum Cost Path with Teleportations
3654 Minimum Sum After Divisible Sum Deletions
3660 Jump Game IX
3661 Maximum Walls Destroyed by Robots
3665 Twisted Mirror Path Count
3670 Maximum Product of Two Integers With No Common Bits
3685 Subsequence Sum After Capping Elements
3686 Number of Stable Subsequences
3693 Climbing Stairs II
3699 Number of ZigZag Arrays I
3700 Number of ZigZag Arrays II
3704 Count No-Zero Pairs That Sum to N
3725 Count Ways to Choose Coprime Integers from Rows
3738 Longest Non-Decreasing Subarray After Replacing at Most One Element
3742 Maximum Path Score in a Grid
3743 Maximize Cyclic Partition Score
3747 Count Distinct Integers After Removing Zeros
3751 Total Waviness of Numbers in Range I
3753 Total Waviness of Numbers in Range II
3757 Number of Effective Subsequences
3772 Maximum Subgraph Score in a Tree
3791 Number of Balanced Integers in a Range
3797 Count Routes to Climb a Rectangular Grid
3801 Minimum Cost to Merge Sorted Lists
3811 Number of Alternating XOR Partitions
3826 Minimum Partition Score
3830 Longest Alternating Subarray After Removing At Most One Element
3836 Maximum Score Using Exactly K Pairs
3840 House Robber V
3844 Longest Almost-Palindromic Substring
3850 Count Sequences to K