state transition dp Pattern
454 problems
Pattern pages help build reusable solving frames. Identify signals first, then explain state, transition, and edge handling.
Recognition Signals
- Do you identify both odd and even length palindromes during center expansion?
- Can you explain how previously computed palindromes reduce redundant checks in the DP table?
- Assess understanding of dynamic programming, especially with state transitions.
Solve Flow
- 1. Define the active state/window.
- 2. Update state while preserving invariants.
- 3. Validate with edge-heavy examples.
Common Misses
- Forgetting to check even-length palindromes, which requires treating centers between characters.
- Failing to handle edge cases like empty string `s` or pattern `p` properly.
- Failing to properly balance the number of opening and closing parentheses during backtracking leads to invalid sequences.
Recommended Ladder
Longest Palindromic Substring
Find the longest contiguous palindromic substring in a given string using dynamic programming and two-pointer expansion …
Regular Expression Matching
The Regular Expression Matching problem involves checking if a string matches a pattern using '.' and '*'.
Generate Parentheses
Generate Parentheses requires generating all valid combinations of parentheses with given pairs using backtracking and s…
Longest Valid Parentheses
Compute the length of the longest well-formed parentheses substring using state transition dynamic programming and stack…
Trapping Rain Water
Calculate the total trapped rain water using the elevation map array, leveraging dynamic programming and two-pointer pat…
Wildcard Matching
Implement full wildcard pattern matching using '?' and '*' by applying state transition dynamic programming with careful…
Jump Game II
Jump Game II requires finding the minimum jumps to reach the end of an array using dynamic programming and greedy techni…
Maximum Subarray
Maximum Subarray is a classic state transition dynamic programming problem about deciding whether to extend or restart a…
Jump Game
Solve the Jump Game problem using state transition dynamic programming to determine if you can reach the last index of t…
Unique Paths
Calculate the number of unique paths for a robot to move on an m x n grid with only right and down movements.
Unique Paths II
Calculate the number of unique paths from top-left to bottom-right in a grid with obstacles using dynamic programming st…
Minimum Path Sum
Compute the minimum sum from top-left to bottom-right in a grid using state transition dynamic programming efficiently.
Climbing Stairs
Climbing Stairs is a classic dynamic programming problem where you calculate distinct ways to reach the top using step t…
Edit Distance
Determine the minimum number of insertions, deletions, or replacements to transform one string into another using dynami…
Maximal Rectangle
Compute the largest rectangle of 1's in a binary matrix using dynamic programming and stack-based state transitions effi…
Scramble String
Scramble String is a dynamic programming problem where we determine if one string can be scrambled to form another using…
Decode Ways
Decode Ways is a dynamic programming problem focused on decoding a numeric string to letters using specific mappings.
Interleaving String
The Interleaving String problem requires determining if a string can be formed by interleaving two others, utilizing dyn…
Distinct Subsequences
Compute the number of distinct subsequences of one string matching another using precise state transition dynamic progra…
Pascal's Triangle
Generate the first numRows of Pascal's Triangle using dynamic programming with clear state transitions and array manipul…
Pascal's Triangle II
Compute the specific row of Pascal's Triangle using efficient state transition dynamic programming with array-based upda…
Triangle
Given a triangle, return the minimum path sum from top to bottom, moving to adjacent numbers in the row below.
Best Time to Buy and Sell Stock
Maximize stock profit by identifying the optimal buy and sell days using dynamic programming.
Best Time to Buy and Sell Stock II
Maximize stock profit by using a greedy approach to buy and sell multiple times, with state transition dynamic programmi…
Best Time to Buy and Sell Stock III
Determine the maximum profit from at most two stock transactions using state transition dynamic programming on price arr…
Palindrome Partitioning
Find all possible palindrome partitioning of a string using backtracking and dynamic programming.
Palindrome Partitioning II
Determine the minimum cuts required to partition a string into all palindromic substrings using dynamic programming tech…
Maximum Product Subarray
Find the subarray with the largest product in an integer array using dynamic programming techniques.
Dungeon Game
Calculate the minimum initial health the knight needs to survive the dungeon using state transition dynamic programming …
Best Time to Buy and Sell Stock IV
Determine the maximum profit from at most k stock transactions using state transition dynamic programming on an array of…
House Robber
Maximize the amount of money you can rob tonight without alerting the police by applying dynamic programming with state …
House Robber II
Maximize your loot by robbing houses arranged in a circle without alerting the police using dynamic programming.
Maximal Square
Maximal Square is a matrix-based dynamic programming problem that focuses on finding the largest square filled with 1's.
Number of Digit One
Compute the total number of digit one appearing in all numbers from 0 up to n using state transition dynamic programming…
Different Ways to Add Parentheses
Solve Different Ways to Add Parentheses by splitting on each operator and memoizing every subexpression result list.
Ugly Number II
Find the nth ugly number, where ugly numbers have prime factors limited to 2, 3, and 5.
Perfect Squares
Perfect Squares asks for the least number of perfect squares summing to a given integer n using dynamic programming or B…
Longest Increasing Subsequence
Solve the Longest Increasing Subsequence problem using dynamic programming and binary search to efficiently find the sub…
Best Time to Buy and Sell Stock with Cooldown
Maximize stock profit with cooldown restrictions using state transition dynamic programming to track buy, sell, and cool…
Burst Balloons
Burst Balloons is a hard dynamic programming problem requiring careful state transitions to maximize coins collected eff…
Super Ugly Number
Compute the nth super ugly number efficiently using dynamic programming with state transitions based on the given prime …
Coin Change
Find the minimum number of coins needed to reach a target amount using dynamic programming state transitions efficiently…
Counting Bits
Compute the number of 1 bits for every integer from 0 to n using state transition dynamic programming for efficiency.
Integer Break
Break an integer into the sum of positive integers to maximize the product using dynamic programming.
Russian Doll Envelopes
Russian Doll Envelopes is a dynamic programming problem that involves finding the longest chain of envelopes that can be…
Count Numbers with Unique Digits
The problem asks to count numbers with unique digits from 0 to 10^n using dynamic programming, math, and backtracking te…
Largest Divisible Subset
Find the largest subset of distinct positive integers where every pair satisfies divisibility using state transition dyn…
Guess Number Higher or Lower II
Minimize the maximum cost of guessing a number in a dynamic guessing game using optimal strategies.
Wiggle Subsequence
Find the longest wiggle subsequence in an integer array using state transition dynamic programming with greedy optimizat…
Combination Sum IV
Combination Sum IV asks to find the number of combinations that sum to a given target using elements from an array.
Is Subsequence
Determine if one string is a subsequence of another using state transition dynamic programming for accurate character ma…
Rotate Function
Maximize the rotation function by rotating the array and calculating the weighted sum for all rotations.
Integer Replacement
Find the minimum number of operations to reduce a number to 1 by applying specific operations, using state transition dy…
Frog Jump
Determine if a frog can cross a river using jumps constrained by previous step sizes in a dynamic programming state tran…
Split Array Largest Sum
Solve the 'Split Array Largest Sum' problem by minimizing the largest sum across k subarrays using dynamic programming a…
Arithmetic Slices
Count the number of arithmetic subarrays in a given integer array using dynamic programming.
Partition Equal Subset Sum
Determine if an array can be partitioned into two subsets with equal sum using dynamic programming techniques.
Non-overlapping Intervals
Determine the minimum number of intervals to remove from a list to ensure no intervals overlap using dynamic programming…
Arithmetic Slices II - Subsequence
Count all arithmetic subsequences in an array using dynamic programming with precise state transitions for correctness.
Poor Pigs
Find the minimum number of pigs required to determine the poisonous bucket within a set time using state transition dyna…
Can I Win
Determine if the first player can guarantee a win in a turn-based number selection game using state transition dynamic p…
Count The Repetitions
This problem requires counting how many times a repeated string s2 fits as a subsequence within a repeated string s1 usi…
Unique Substrings in Wraparound String
Solve the 'Unique Substrings in Wraparound String' problem using dynamic programming with a state transition approach.
Concatenated Words
Find concatenated words by using dynamic programming and depth-first search to identify valid words made of other words …
Matchsticks to Square
The problem asks to determine if we can use matchsticks to form a square, exploring dynamic programming and backtracking…
Ones and Zeroes
Solve the Ones and Zeroes problem using dynamic programming with state transition, focusing on array and string manipula…
Predict the Winner
Predict the Winner involves two players taking turns to maximize their score by picking from either end of an array, opt…
Zuma Game
The Zuma Game involves clearing balls from the board using a limited hand, applying dynamic programming and state transi…
Target Sum
Target Sum requires counting all expressions from nums using '+' or '-' that evaluate exactly to the given target intege…
Fibonacci Number
Calculate the nth Fibonacci number using state transition dynamic programming and recursive techniques efficiently in in…
Freedom Trail
Determine the minimum rotations and button presses to spell a keyword on a circular dial using state transition dynamic …
Longest Palindromic Subsequence
Find the length of the longest palindromic subsequence in a string using precise state transition dynamic programming.
Coin Change II
Calculate the number of unique coin combinations to reach a target amount using state transition dynamic programming eff…
Beautiful Arrangement
The Beautiful Arrangement problem asks for the number of valid permutations of n integers satisfying specific divisibili…
01 Matrix
The '01 Matrix' problem challenges you to find the nearest zero for each cell in a binary matrix using dynamic programmi…
Remove Boxes
Maximize points by strategically removing contiguous same-colored boxes using state transition dynamic programming and m…
Student Attendance Record II
The Student Attendance Record II problem explores counting valid student attendance sequences using dynamic programming …
Optimal Division
Maximize the value of an expression by optimally placing parentheses for division operations.
Out of Boundary Paths
Calculate the number of ways a ball can exit a grid using dynamic programming with state transitions for every move comb…
Delete Operation for Two Strings
Find the minimum number of steps to make two strings equal by deleting characters, using dynamic programming.
Non-negative Integers without Consecutive Ones
Count non-negative integers up to n without consecutive ones in their binary representation using dynamic programming.
K Inverse Pairs Array
The K Inverse Pairs Array problem focuses on counting arrays with exactly k inverse pairs using dynamic programming.
Shopping Offers
Minimize the cost of purchasing items using available special offers with state transition dynamic programming.
Decode Ways II
Decode Ways II is a challenging dynamic programming problem that involves decoding messages with digits and wildcard cha…
Maximum Length of Pair Chain
Determine the maximum length of a chain formed by pairs using dynamic programming and greedy sorting techniques efficien…
Palindromic Substrings
Count all palindromic substrings in a given string using state transition dynamic programming for efficient evaluation.
2 Keys Keyboard
Minimize the number of operations to get exactly 'n' characters on the screen using two operations: Copy All and Paste.
Strange Printer
Calculate the minimum turns a strange printer needs to print any string using state transition dynamic programming effic…
Number of Longest Increasing Subsequence
This problem challenges you to find the number of longest increasing subsequences in a given array of integers.
Valid Parenthesis String
Solve the Valid Parenthesis String problem by leveraging state transition dynamic programming to handle parentheses and …
Knight Probability in Chessboard
Calculate the probability that a knight remains on an n x n chessboard after making exactly k moves using dynamic progra…
Maximum Sum of 3 Non-Overlapping Subarrays
Maximize the sum of three non-overlapping subarrays with length k in an integer array using dynamic programming.
Partition to K Equal Sum Subsets
Determine if an integer array can be partitioned into k subsets where each subset sums to the same value using DP and ba…
Minimum ASCII Delete Sum for Two Strings
This problem focuses on minimizing the ASCII delete sum for two strings by using dynamic programming to find the lowest …
Best Time to Buy and Sell Stock with Transaction Fee
Maximize stock trading profits accounting for per-transaction fees using state transition dynamic programming and greedy…
Maximum Length of Repeated Subarray
Find the maximum length of a subarray that appears in both given integer arrays using dynamic programming.
Count Different Palindromic Subsequences
Count Different Palindromic Subsequences leverages dynamic programming to count non-empty palindromic subsequences in a …
Cherry Pickup
Maximize cherries collected on a grid, employing state transition dynamic programming with careful navigation across obs…
Min Cost Climbing Stairs
Compute the minimum cost to reach the top of a staircase using dynamic programming and step-by-step state transitions ef…
Largest Plus Sign
Find the largest axis-aligned plus sign in a binary grid with some mines using dynamic programming.
Sliding Puzzle
Determine the minimum moves to solve a 2x3 sliding puzzle using BFS and state transition dynamic programming techniques …
Rotated Digits
Count all integers from 1 to n that transform into a different valid number when each digit is rotated 180 degrees using…
Domino and Tromino Tiling
Calculate the number of ways to tile a 2xN board using dominoes and trominoes with precise state transitions.
Champagne Tower
Compute champagne levels in a pyramid of glasses using state transition dynamic programming for accurate distribution tr…
Minimum Swaps To Make Sequences Increasing
This problem involves finding the minimum number of swaps needed to make two sequences strictly increasing using dynamic…
Split Array With Same Average
Determine whether an integer array can be partitioned into two non-empty subarrays with the same average using dynamic p…
Soup Servings
Compute the probability that soup A empties before soup B using state transition dynamic programming efficiently.
Largest Sum of Averages
Maximize the sum of averages by partitioning an integer array into at most k contiguous subarrays using dynamic programm…
Race Car
Race Car is a dynamic programming problem where the goal is to find the shortest sequence of instructions to reach a tar…
Count Unique Characters of All Substrings of a Given String
Calculate the sum of unique characters in all substrings of a string using state transition dynamic programming.
New 21 Game
Calculate the probability Alice reaches at most n points using state transition dynamic programming efficiently.
Push Dominoes
In the "Push Dominoes" problem, you simulate the falling dominoes based on their initial states and determine their fina…
Longest Mountain in Array
Find the length of the longest subarray forming a mountain pattern using state transitions and two-pointer logic efficie…
Minimum Number of Refueling Stops
Determine the minimum number of refueling stops needed to reach a target using dynamic programming and greedy strategies…
Stone Game
Stone Game is a dynamic programming problem where players alternate taking stones from piles to maximize their score.
Profitable Schemes
Given a group of members and a list of crimes, count the profitable schemes that meet the profit and group constraints.
Super Egg Drop
Solve the Super Egg Drop problem using dynamic programming and binary search to minimize the number of moves required to…
Bitwise ORs of Subarrays
Compute the number of unique bitwise OR values from all non-empty subarrays using dynamic state transitions efficiently.
Numbers At Most N Given Digit Set
The 'Numbers At Most N Given Digit Set' problem requires calculating how many numbers can be formed using a given digit …
Valid Permutations for DI Sequence
The problem asks to find the number of valid permutations for a given DI sequence string using dynamic programming and s…
Sum of Subarray Minimums
Calculate the sum of minimum values across all subarrays of a given array modulo 10^9 + 7.
Maximum Sum Circular Subarray
Find the maximum sum of a circular subarray using state transition dynamic programming, optimizing for wraparound cases …
Number of Music Playlists
Solve the Number of Music Playlists problem with dynamic programming, focusing on state transitions and combinatorics to…
Flip String to Monotone Increasing
Minimize the number of flips needed to make a binary string monotone increasing using dynamic programming.
Minimum Falling Path Sum
Minimum Falling Path Sum is a matrix dynamic programming problem where each cell depends on three reachable cells above …
Knight Dialer
Solve the Knight Dialer problem using state transition dynamic programming to efficiently calculate valid number paths f…
Distinct Subsequences II
Find the number of distinct non-empty subsequences of a string using dynamic programming and state transitions.
Find the Shortest Superstring
This problem requires constructing the shortest string containing all input words using state transition dynamic program…
Tallest Billboard
Solve the Tallest Billboard problem by using dynamic programming to find the maximum equal height for two disjoint rod s…
Delete Columns to Make Sorted III
The problem requires minimizing deletions to ensure all strings are lexicographically sorted. Use dynamic programming fo…
Least Operators to Express Number
Compute the minimum number of arithmetic operators to form a target using repeated x with addition, subtraction, multipl…
Odd Even Jump
Determine the number of valid starting indices in an array where you can reach the end with alternating odd and even jum…
Longest Turbulent Subarray
Find the length of the longest subarray where element comparisons alternate, using state transition dynamic programming …
Minimum Cost For Tickets
Solve the Minimum Cost For Tickets problem using state transition dynamic programming for optimal travel ticket purchase…
Minimum Cost to Merge Stones
Minimize the cost to merge stones with k consecutive piles using dynamic programming to achieve the optimal solution.
Numbers With Repeated Digits
Solve Numbers With Repeated Digits by counting unique-digit numbers up to n, then subtracting from n using digit DP.
Best Sightseeing Pair
Compute the maximum sightseeing score efficiently using state transition dynamic programming and single-pass array itera…
Video Stitching
Solve the "Video Stitching" problem using state transition dynamic programming to cover a sporting event with minimum cl…
Divisor Game
Divisor Game is a game theory problem where players take turns subtracting divisors of a number n until one player loses…
Maximum Sum of Two Non-Overlapping Subarrays
Find the maximum sum of two non-overlapping subarrays by efficiently using state transition dynamic programming.
Uncrossed Lines
The Uncrossed Lines problem involves finding the maximum number of non-intersecting lines that can be drawn between two …
Minimum Score Triangulation of Polygon
Compute the minimum total score to triangulate a convex polygon using state transition dynamic programming on vertex val…
Partition Array for Maximum Sum
Partition an array into subarrays of length at most k, replacing each with its maximum to maximize total sum efficiently…
Last Stone Weight II
In the 'Last Stone Weight II' problem, you need to find the minimal possible stone weight after a series of smashes usin…
Shortest Common Supersequence
Compute the shortest string containing both given strings as subsequences using state transition dynamic programming eff…
Filling Bookcase Shelves
Determine the minimum total height of a bookcase by placing books in order using state transition dynamic programming.
Smallest Sufficient Team
Find the smallest subset of people covering all required skills using bitmask dynamic programming for efficient state tr…
Minimum Cost Tree From Leaf Values
Compute the minimum sum of non-leaf nodes in a binary tree formed from array leaves using dynamic programming efficientl…
N-th Tribonacci Number
Compute the N-th Tribonacci number using state transition dynamic programming with careful memoization and iterative upd…
Largest 1-Bordered Square
Find the largest square of 1s with 1s on its borders in a binary grid using dynamic programming.
Stone Game II
Stone Game II is a dynamic programming problem where Alice and Bob alternate taking stones from piles to maximize their …
Longest Common Subsequence
Find the length of the longest common subsequence between two strings using state transition dynamic programming for eff…
Longest Chunked Palindrome Decomposition
Solve the "Longest Chunked Palindrome Decomposition" problem by using dynamic programming and string manipulation techni…
Number of Dice Rolls With Target Sum
Calculate the number of ways to roll n dice with k faces to reach a target sum using state transition dynamic programmin…
As Far from Land as Possible
Find the farthest water cell from land in a grid and return the Manhattan distance using state transition dynamic progra…
Maximum Subarray Sum with One Deletion
Find the maximum sum of a subarray with at most one deletion in this dynamic programming problem.
Make Array Strictly Increasing
Determine the minimum operations to transform arr1 into a strictly increasing sequence using values from arr2 efficientl…
K-Concatenation Maximum Sum
Solve the K-Concatenation Maximum Sum problem using dynamic programming and optimal sub-array sum calculation.
Count Vowels Permutation
Count Vowels Permutation requires computing the number of valid vowel strings of length n using state transition dynamic…
Dice Roll Simulation
Calculate all valid sequences of n dice rolls with consecutive roll constraints using state transition dynamic programmi…
Airplane Seat Assignment Probability
Calculate the probability that the last passenger sits in their assigned seat using state transition dynamic programming…
Maximum Profit in Job Scheduling
Compute the maximum profit from non-overlapping jobs using state transition dynamic programming with sorted arrays and b…
Maximum Score Words Formed by Letters
Calculate the highest total score by selecting words from a list using available letters, respecting individual letter s…
Greatest Sum Divisible by Three
Find the maximum sum divisible by three from a given array using dynamic programming and state transition.
Number of Ways to Stay in the Same Place After Some Steps
Compute the exact number of ways to remain at index 0 after given steps using state transition dynamic programming.
Count Square Submatrices with All Ones
Count the number of square submatrices with all ones in a given binary matrix using dynamic programming.
Palindrome Partitioning III
Find the minimal character changes to split a string into k palindromes using precise dynamic programming state transiti…
Minimum Falling Path Sum II
Find the minimum sum of a falling path in a square matrix using dynamic programming while avoiding same-column selection…
Number of Paths with Max Score
Calculate the maximum score path and count all valid routes in a square board with obstacles using dynamic programming.
Minimum Insertion Steps to Make a String Palindrome
The problem asks to find the minimum number of insertions to convert a string into a palindrome using dynamic programmin…
Minimum Distance to Type a Word Using Two Fingers
Calculate the minimum total distance to type a word using two fingers on a keyboard, applying dynamic programming.
Minimum Number of Taps to Open to Water a Garden
Determine the minimum number of taps to water an entire garden using state transition dynamic programming and interval c…
Find the City With the Smallest Number of Neighbors at a Threshold Distance
Find the city with the fewest neighbors within a given threshold distance using dynamic programming.
Minimum Difficulty of a Job Schedule
Schedule jobs into multiple days to minimize the difficulty of the schedule using dynamic programming and state transiti…
Jump Game V
Jump Game V is a hard dynamic programming problem that focuses on maximizing jumps between indices in an array.
Maximum Students Taking Exam
Calculate the maximum number of students who can take an exam without cheating using state transition dynamic programmin…
Count All Valid Pickup and Delivery Options
Count all valid pickup and delivery sequences for n orders where deliveries occur after pickups using dynamic programmin…
Largest Multiple of Three
Find the largest number divisible by three by selecting and ordering digits optimally using state transition dynamic pro…
Sort Integers by The Power Value
Sort integers in a range based on their power value using dynamic programming and memoization, handling ties with ascend…
Pizza With 3n Slices
Maximize your pizza slice sum from a 3n-sized circular array using state transition dynamic programming efficiently.
Count Number of Teams
Count the number of valid three-soldier teams using ratings with a state transition dynamic programming approach efficie…
Find All Good Strings
Find all good strings between two given strings without including a specified evil substring using dynamic programming.
Reducing Dishes
Maximize the sum of like-time coefficients by optimally choosing dishes to prepare in this dynamic programming problem.
Stone Game III
Stone Game III is a challenging dynamic programming problem based on game theory and state transition logic.
Number of Ways to Paint N × 3 Grid
Calculate the number of ways to paint a grid of size n x 3 with distinct adjacent colors using dynamic programming.
Restore The Array
Calculate the number of arrays that can be restored from a string of digits where each number is within [1, k].
Build Array Where You Can Find The Maximum Exactly K Comparisons
This problem asks to build an array where the maximum element is found using exactly K comparisons, with dynamic program…
Constrained Subsequence Sum
Solve the Constrained Subsequence Sum problem using dynamic programming, sliding window, and priority queues to maximize…
Number of Ways to Wear Different Hats to Each Other
Calculate all unique assignments of hats to people using state transition dynamic programming with bitmasking for collis…
Number of Ways of Cutting a Pizza
This problem challenges you to determine the number of valid ways to cut a pizza into pieces with apples using dynamic p…
Form Largest Integer With Digits That Add up to Target
Maximize the integer you can paint with given digit costs under a target sum, using dynamic programming to optimize the …
Max Dot Product of Two Subsequences
Solve Max Dot Product of Two Subsequences with state transition dynamic programming that enforces a non-empty pairing de…
Cherry Pickup II
Maximize cherry collection in a grid using two robots with careful state transition dynamic programming to optimize path…
Probability of a Two Boxes Having The Same Number of Distinct Balls
Compute the probability that two boxes contain the same number of distinct balls using careful combinatorial and DP meth…
Paint House III
Solve Paint House III using state transition dynamic programming to minimize painting costs while forming exact neighbor…
Allocate Mailboxes
Allocate k mailboxes to houses along a street minimizing total distance using dynamic programming with state transitions…
Longest Subarray of 1's After Deleting One Element
Solve LeetCode 1493 by tracking runs of 1s around one deletion using a tight sliding window or state transition DP.
Parallel Courses II
Determine the minimum semesters to complete all courses with prerequisites using state transition dynamic programming an…
Count Submatrices With All Ones
Count Submatrices With All Ones is a dynamic programming problem focusing on submatrix counting using an efficient row-b…
Stone Game IV
Stone Game IV requires predicting the winner using state transition dynamic programming with careful consideration of pe…
Number of Sub-arrays With Odd Sum
Count the number of subarrays with an odd sum using dynamic programming and prefix sum techniques.
Number of Good Ways to Split a String
Count all valid splits of a string where left and right substrings have equal distinct characters, using efficient state…
Minimum Number of Increments on Subarrays to Form a Target Array
The problem asks for the minimum number of operations to transform an initial array of zeros into a target array using s…
String Compression II
Solve String Compression II with dynamic programming that tracks deletions, run boundaries, and digit-length jumps in co…
Get the Maximum Score
Find the maximum possible score from two sorted arrays with a dynamic programming approach, leveraging partitioning and …
Minimum Cost to Cut a Stick
Find the minimum cost to cut a stick into segments at specified positions using dynamic programming and sorting.
Minimum Number of Days to Eat N Oranges
Find the minimum number of days to eat n oranges using state transition dynamic programming with memoization.
Stone Game V
In Stone Game V, Alice divides stones into rows to maximize her score, using a dynamic programming approach to try all d…
Maximum Length of Subarray With Positive Product
Given an array, find the maximum length of a subarray with a positive product using dynamic programming.
Count All Possible Routes
This problem requires counting all possible routes between cities using fuel efficiently with state transition dynamic p…
Minimum Time to Make Rope Colorful
Minimize the time Bob needs to remove balloons to make a rope colorful using dynamic programming with state transitions.
Maximum Non Negative Product in a Matrix
Find the maximum non-negative product path in a matrix using dynamic programming and state transition.
Minimum Cost to Connect Two Groups of Points
Compute the minimum cost to fully connect two groups of points using dynamic programming and bitmasking efficiently.
Minimum One Bit Operations to Make Integers Zero
Compute the minimum number of one-bit operations to convert a given integer to zero using state transition dynamic progr…
Number of Sets of K Non-Overlapping Line Segments
Count all valid arrangements of k non-overlapping line segments on n points using state transition dynamic programming.
Best Team With No Conflicts
Find the highest score basketball team by choosing players without conflicts in age and score using dynamic programming.
Count Substrings That Differ by One Character
Count all substrings from s that differ by exactly one character from some substring in t using precise substring compar…
Number of Ways to Form a Target String Given a Dictionary
Calculate the number of ways to form a target string using words of equal length via state transition dynamic programmin…
Count Sorted Vowel Strings
Calculate the number of length-n strings with vowels only that are sorted lexicographically using state transitions.
Kth Smallest Instructions
Find the kth smallest lexicographic instruction sequence for reaching a destination in a grid using state transition dyn…
Minimum Deletions to Make String Balanced
Determine the minimum number of deletions to transform a string of 'a' and 'b' into a balanced order using DP.
Minimum Jumps to Reach Home
Find the minimum number of jumps needed to reach a target position while avoiding forbidden positions.
Distribute Repeating Integers
Determine if you can allocate integers to satisfy customer quantities using state transition dynamic programming techniq…
Maximize Grid Happiness
Maximize Grid Happiness is a dynamic programming problem focusing on state transitions with bitmasking to maximize happi…
Maximum Repeating Substring
Find the maximum number of times a given word repeats consecutively in a string using state transition dynamic programmi…
Minimum Number of Removals to Make Mountain Array
Solve the problem of finding the minimum number of removals to make a given array a mountain array using dynamic program…
Minimum Incompatibility
Optimize the sum of incompatibilities when distributing an array into subsets with unique elements.
Delivering Boxes from Storage to Ports
Optimize the minimum number of trips to deliver boxes to ports under strict ship constraints using dynamic programming t…
Stone Game VII
Maximize score difference in a two-player turn-based stone removal game using state transition dynamic programming.
Maximum Height by Stacking Cuboids
Maximize the height of stacked cuboids by strategically rotating and stacking them using dynamic programming.
Jump Game VI
Jump Game VI challenges you to maximize your score while jumping through an array using state transition dynamic program…
Find Minimum Time to Finish All Jobs
Minimize the maximum working time of k workers by optimally assigning jobs, leveraging dynamic programming and bit manip…
Count Ways to Make Array With Product
Determine the number of arrays of size n where the product equals k using prime factorization and combinatorial DP techn…
Palindrome Partitioning IV
The Palindrome Partitioning IV problem asks you to determine if a string can be split into three palindromic substrings.
Maximum Absolute Sum of Any Subarray
Solve for the maximum absolute sum of any subarray using dynamic programming and understanding state transitions.
Maximum Number of Events That Can Be Attended II
Determine the maximum sum of event values you can collect by attending at most k non-overlapping events using DP.
Closest Subsequence Sum
Find the minimum absolute difference between a target goal and any subsequence sum using optimized dynamic programming a…
Maximum Score from Performing Multiplication Operations
Solve the Maximum Score from Performing Multiplication Operations problem using dynamic programming and state transition…
Maximize Palindrome Length From Subsequences
Maximize Palindrome Length From Subsequences explores dynamic programming to construct the longest palindrome from two s…
Closest Dessert Cost
Find the closest dessert cost to a target by selecting from a list of base flavors and topping combinations using dynami…
Make the XOR of All Segments Equal to Zero
Determine the minimum changes needed in an array so all size-k segments XOR to zero using DP and bit manipulation.
Maximize Score After N Operations
Maximize the score after n operations by selecting pairs from the array and using their GCD with dynamic programming or …
Maximum Number of Groups Getting Fresh Donuts
Reorder groups to maximize happy customers by using state transition dynamic programming with bitmasking for optimal bat…
Minimum Sideway Jumps
Solve the Minimum Sideway Jumps problem using state transition dynamic programming to minimize side jumps while navigati…
Number of Ways to Rearrange Sticks With K Sticks Visible
Calculate the number of arrangements of n uniquely-sized sticks so exactly k sticks are visible using dynamic programmin…
Jump Game VII
The problem asks to determine if we can reach the last index of a binary string, with a set range of jumps between indic…
Stone Game VIII
Stone Game VIII requires calculating maximum score difference using state transition dynamic programming on prefix sums …
Minimum XOR Sum of Two Arrays
Minimize the XOR sum of two integer arrays by rearranging elements using dynamic programming and bit manipulation.
Minimum Skips to Arrive at Meeting On Time
Solve the problem of minimizing skips while traveling to arrive on time, using dynamic programming and state transitions…
Egg Drop With 2 Eggs and N Floors
Determine the minimum drops needed to find the critical floor using 2 eggs with optimized state transition dynamic progr…
Minimum Number of Flips to Make the Binary String Alternating
Find the minimum number of flips to make a binary string alternate, using state transition dynamic programming.
Minimum Cost to Change the Final Value of Expression
Determine the minimum operations to change a boolean expression's result using state transition dynamic programming effi…
The Earliest and Latest Rounds Where Players Compete
This problem requires finding the earliest and latest rounds where two players compete using dynamic programming with st…
Maximum Alternating Subsequence Sum
Maximize alternating subsequence sum with dynamic programming and state transitions in an array.
Minimum Cost to Reach Destination in Time
Minimize the travel cost in a graph while adhering to a time constraint using state transition dynamic programming.
Painting a Grid With Three Different Colors
Count the number of ways to paint a grid using three colors while ensuring adjacent cells have different colors.
Maximum Number of Points with Cost
Maximize your points in a matrix by selecting cells row by row while accounting for distance penalties using dynamic pro…
Maximum Compatibility Score Sum
Assign students to mentors to maximize total compatibility using state transition dynamic programming with bitmask optim…
Count Number of Special Subsequences
Learn to count all valid special subsequences in an array using state transition dynamic programming efficiently and cor…
Minimum Total Space Wasted With K Resizing Operations
Find the minimum total space wasted in a dynamic array with at most k resizing operations.
Number of Ways to Separate Numbers
Calculate the number of valid non-decreasing integer sequences from a string using state transition dynamic programming …
Minimize the Difference Between Target and Chosen Elements
This problem asks to select one element per row to minimize the absolute difference from a target sum using dynamic prog…
Minimum Number of Work Sessions to Finish the Tasks
Find the minimum number of work sessions needed to finish a set of tasks, considering task durations and session time.
Number of Unique Good Subsequences
Find the number of unique good subsequences of a binary string using dynamic programming and modular arithmetic.
First Day Where You Have Been in All the Rooms
Calculate the first day you have visited all rooms using state transition dynamic programming on the nextVisit array.
Maximum Product of the Length of Two Palindromic Subsequences
Find two disjoint palindromic subsequences in a string to maximize the product of their lengths efficiently using dynami…
The Score of Students Solving Math Expression
Calculate student scores for a single-digit math expression using state transition dynamic programming to track all vali…
Partition Array Into Two Arrays to Minimize Sum Difference
Partition an integer array into two equal halves to minimize the absolute difference of their sums using dynamic program…
Two Best Non-Overlapping Events
Maximize the total value of at most two non-overlapping events using state transition dynamic programming efficiently.
Check if an Original String Exists Given Two Encoded Strings
Determine if there exists an original string that could produce both encoded inputs using state transition dynamic progr…
Vowels of All Substrings
Compute the total number of vowels in all substrings of a given string using efficient state transition dynamic programm…
Minimum Number of Food Buckets to Feed the Hamsters
Find the minimum number of food buckets required to feed all hamsters, using dynamic programming and greedy techniques.
Count Fertile Pyramids in a Land
Solve Count Fertile Pyramids in a Land with matrix DP that measures the tallest pyramid rooted at each fertile cell.
Find Good Days to Rob the Bank
Find good days to rob the bank by identifying days with non-increasing and non-decreasing guard counts using dynamic pro…
Number of Smooth Descent Periods of a Stock
Count all contiguous periods where stock prices descend smoothly by exactly one using dynamic programming techniques.
Solving Questions With Brainpower
Maximize points in an exam with state transition dynamic programming by deciding whether to solve or skip each question.
Number of Ways to Divide a Long Corridor
Calculate the number of ways to split a corridor into sections with exactly two seats using dynamic programming efficien…
Minimum Difference in Sums After Removal of Elements
Minimize the difference between sums after removing n elements from a 3n array by dividing the remaining elements into t…
Minimum Time to Remove All Cars Containing Illegal Goods
Determine the minimum time to remove all cars with illegal goods using state transition dynamic programming efficiently.
Maximum AND Sum of Array
Find the maximum AND sum by placing integers into limited slots using state transition dynamic programming efficiently.
Minimum Time to Finish the Race
Minimize the time to complete a race with tire swaps using dynamic programming and state transitions.
Minimum White Tiles After Covering With Carpets
Find the minimum number of white tiles visible after optimally placing carpets using state transition dynamic programmin…
Maximum Value of K Coins From Piles
Optimize coin selection across multiple piles using state transition dynamic programming to achieve the maximum wallet v…
Number of Ways to Select Buildings
Solve Number of Ways to Select Buildings by counting alternating 3-building patterns with state transitions over the bin…
Total Appeal of A String
Calculate the total appeal of all substrings by counting distinct characters efficiently using state transition DP and h…
Count Number of Texts
Calculate the total number of possible original texts from a pressed key sequence using state transition dynamic program…
Check if There Is a Valid Parentheses String Path
Check if there exists a valid parentheses string path in a given grid using state transition dynamic programming.
Substring With Largest Variance
Find the largest variance possible in any substring of a given string using dynamic programming.
Minimum Path Cost in a Grid
Minimize the cost of a path in a grid while considering move costs for each step.
Fair Distribution of Cookies
The problem focuses on fairly distributing cookies among children to minimize the maximum unfairness of the distribution…
Sum of Numbers With Units Digit K
Determine the minimum set of positive integers whose units digits match k and sum exactly to num using DP patterns.
Longest Binary Subsequence Less Than or Equal to K
Find the longest subsequence in a binary string that forms a number less than or equal to a given integer k.
Selling Pieces of Wood
Maximize your profit by cutting a wooden piece into smaller parts based on given prices and dimensions.
Number of Distinct Roll Sequences
Calculate the number of distinct sequences of dice rolls based on specific conditions using dynamic programming.
Count Number of Ways to Place Houses
This problem asks you to calculate the number of ways to place houses along a street while preventing adjacent houses on…
Maximum Score Of Spliced Array
Maximize the score of two arrays by splicing and swapping a subarray using dynamic programming.
Number of People Aware of a Secret
Calculate how many people know a secret over n days using state transition dynamic programming and careful simulation of…
Count the Number of Ideal Arrays
This problem involves counting the number of ideal arrays of a given length under certain conditions using state transit…
Check if There is a Valid Partition For The Array
This problem challenges you to determine if an array can be partitioned into valid subarrays using dynamic programming.
Longest Ideal Subsequence
The Longest Ideal Subsequence problem involves finding the longest subsequence where each character has a difference of …
Count Special Integers
Count the number of special integers in the interval [1, n] where digits of each integer are distinct.
Time Needed to Rearrange a Binary String
Calculate the exact seconds required to convert all 01 pairs into 10 in a binary string using state transitions.
Number of Ways to Reach a Position After Exactly k Steps
Find the number of ways to reach a position after exactly k steps on an infinite number line using dynamic programming.
Longest Increasing Subsequence II
Determine the longest increasing subsequence in an array where consecutive elements differ by at most k using dynamic pr…
Find All Good Indices
Identify all indices in an array where the k-length prefix is non-increasing and the k-length suffix is non-decreasing.
Maximum Deletions on a String
Find the maximum number of deletions on a string using state transition dynamic programming and rolling hash techniques …
Paths in Matrix Whose Sum Is Divisible by K
Compute all paths in a matrix where the sum of elements is divisible by k using state transition dynamic programming eff…
Minimize Maximum of Array
Minimize Maximum of Array involves finding the smallest possible maximum value after applying a series of operations on …
Minimum Total Distance Traveled
Optimize the total distance traveled by robots to factories using dynamic programming, sorting, and state transitions.
Count Ways To Build Good Strings
Count the number of ways to build good binary strings using dynamic programming with state transitions.
Maximum Number of Non-overlapping Palindrome Substrings
Find the maximum number of non-overlapping palindromic substrings of at least length k in a string using dynamic program…
Number of Beautiful Partitions
The problem involves finding the number of beautiful partitions in a string with dynamic programming and state transitio…
Count Palindromic Subsequences
Count the number of palindromic subsequences of length 5 in a given string of digits.
Number of Great Partitions
Calculate the number of great partitions of an array using state transition dynamic programming with careful sum constra…
Partition String Into Substrings With Values at Most K
Determine the minimum number of substrings from a numeric string such that each substring value does not exceed k using …
Count Increasing Quadruplets
Given a permutation of numbers, count the number of increasing quadruplets using dynamic programming.
Disconnect Path in a Binary Matrix by at Most One Flip
Determine if a single cell flip can disconnect a path from the top-left to bottom-right in a binary matrix efficiently u…
House Robber IV
House Robber IV requires calculating minimum maximum money the robber can take using state transition dynamic programmin…
Minimum Operations to Reduce an Integer to 0
Compute the minimum number of operations to reduce a positive integer to zero using additions or subtractions of powers …
Count the Number of Square-Free Subsets
Learn how to efficiently count square-free subsets using state transition dynamic programming with bitmask optimizations…
Find the String with LCP
Determine the lexicographically smallest string matching a given LCP matrix using state transition dynamic programming.
Number of Ways to Earn Points
Find the number of ways to earn exactly target points using multiple types of exam questions with distinct marks.
Minimize the Maximum Difference of Pairs
Minimize the Maximum Difference of Pairs seeks to optimize the maximum pairwise difference in a set of index pairs from …
Minimum Number of Visited Cells in a Grid
Determine the minimum number of cells to visit in a grid using state transition dynamic programming and efficient traver…
Minimum Additions to Make Valid String
Determine the minimum insertions required to transform a given string into repeated concatenations of 'abc' using dynami…
Power of Heroes
Calculate the total power of all non-empty hero groups using state transition dynamic programming efficiently with sorti…
Maximum Number of Moves in a Grid
Maximize the number of moves in a grid starting from the first column using state transition dynamic programming.
Maximum Strength of a Group
Maximize the strength of a student group by carefully selecting students based on their scores, using dynamic programmin…
Minimum Cost to Make All Characters Equal
Find the minimum cost to make all characters of a binary string equal by performing two types of operations.
Count of Integers
Count of Integers challenges you to find the number of integers with a digit sum between a given range using dynamic pro…
Special Permutations
Count the number of special permutations for a given array using dynamic programming and bit manipulation.
Painting the Walls
Compute the minimum cost to paint all walls using a paid and free painter with state transition dynamic programming.
Construct the Longest New String
Maximize the length of a string built from AA, BB, and AB without creating triple repeats using DP and greedy logic.
Decremental String Concatenation
Solve the Decremental String Concatenation problem by applying dynamic programming to minimize string length after conca…
Ways to Split Array Into Good Subarrays
Calculate the number of ways to partition a binary array into good subarrays using state transition dynamic programming …
Partition String Into Minimum Beautiful Substrings
Partition a binary string into the fewest beautiful substrings using state transition dynamic programming and careful su…
Maximum Number of Jumps to Reach the Last Index
Find the maximum number of jumps to reach the last index using state transition dynamic programming efficiently in array…
Longest Non-decreasing Subarray From Two Arrays
Maximize the length of a non-decreasing subarray by optimally choosing elements from two arrays using dynamic programmin…
Visit Array Positions to Maximize Score
Maximize your score by visiting positions in an array while handling penalties for parity changes efficiently with DP.
Ways to Express an Integer as Sum of Powers
Compute the number of ways to express an integer as a sum of unique powers using state transition dynamic programming ef…
Count Stepping Numbers in Range
Count the stepping numbers in a range using dynamic programming with state transitions between digits.
Minimum Time to Make Array Sum At Most x
Calculate the minimum seconds to reduce the array sum to at most x using optimal single-time reductions per index effici…
Check if it is Possible to Split Array
Determine whether an array can be fully split into single-element subarrays using a state transition dynamic programming…
Sorting Three Groups
Determine the minimum removals to make an array of 1s, 2s, and 3s non-decreasing using dynamic programming transitions.
Number of Beautiful Integers in the Range
Count all integers in a given range that have equal even and odd digits and are divisible by k using DP.
Maximize Value of Function in a Ball Passing Game
Maximize the total score in a ball-passing game by selecting the best starting player using state transition dynamic pro…
Minimum Moves to Spread Stones Over Grid
Solve the problem of distributing 9 stones across a 3x3 grid with minimal moves using state transition dynamic programmi…
String Transformation
Find how many ways string s can be transformed into string t in exactly k operations using suffix rotations.
Count Visited Nodes in a Directed Graph
Count Visited Nodes in a Directed Graph uses dynamic programming to solve graph traversal and node visitation counting e…
Apply Operations to Make Two Strings Equal
Apply Operations to Make Two Strings Equal involves transforming binary strings with a cost-based dynamic programming ap…
Longest Unequal Adjacent Groups Subsequence I
Find the longest alternating subsequence in a string array based on a binary group array.
Longest Unequal Adjacent Groups Subsequence II
Find the longest subsequence of indices such that the corresponding strings have a valid Hamming distance and group cons…
Minimum Changes to Make K Semi-palindromes
Minimize the number of letter changes to partition a string into k semi-palindromes using dynamic programming and two po…
Length of the Longest Subsequence That Sums to Target
Find the length of the longest subsequence in an array that sums to a target value, using dynamic programming.
Subarrays Distinct Element Sum of Squares II
Compute the sum of squares of distinct elements in all subarrays using state transition dynamic programming efficiently.
Minimum Increment Operations to Make Array Beautiful
Optimize the number of increment operations to make an array beautiful by ensuring subarrays of size 3 or more meet the …
Maximum Balanced Subsequence Sum
Learn to find the maximum sum of a balanced subsequence using dynamic programming and careful state transitions efficien…
Number of Strings Which Can Be Rearranged to Contain Substring
Calculate how many strings of length n can be rearranged to contain "leet" using dynamic programming and combinatorics.
Minimum Number of Coins for Fruits
Calculate the minimum coins to buy fruits using state transition dynamic programming while handling rewards and purchase…
Find Maximum Non-decreasing Array Length
Solve Find Maximum Non-decreasing Array Length with prefix-sum DP transitions that maximize kept segments while preservi…
Remove Adjacent Almost-Equal Characters
Minimize operations to remove adjacent almost-equal characters using dynamic programming and greedy methods.
Minimum Cost to Convert String II
Compute the minimum cost to transform source into target using substring replacements with given costs efficiently using…
Minimum Number of Operations to Make X and Y Equal
Determine the minimum operations to make two integers equal using increment, decrement, and division efficiently with DP…
Count the Number of Powerful Integers
Count the number of powerful integers in a given range by applying state transition dynamic programming with constraints…
Maximize the Number of Partitions After Operations
Maximizing the number of partitions in a string after changing one character and applying partitioning operations using …
Maximum Number That Sum of the Prices Is Less Than or Equal to K
Find the greatest number whose accumulated price, based on binary set bit positions, is less than or equal to k.
Maximum Number of Operations With the Same Score II
This problem asks to maximize operations on an integer array where all deletions produce the same score using dynamic pr…
Maximize Consecutive Elements in an Array After Modification
Solve Maximize Consecutive Elements in an Array After Modification by sorting and using state transition DP on value and…
Maximum Strength of K Disjoint Subarrays
Solve Maximum Strength of K Disjoint Subarrays with dynamic programming that tracks segment state, sign changes, and wei…
Find the Sum of the Power of All Subsequences
Find the sum of the power of all subsequences of an integer array where their sum equals a given number.
Find the Sum of Subsequence Powers
Compute the sum of powers for all subsequences of length k using state transition dynamic programming efficiently.
Minimum Sum of Values by Dividing Array
Solve the problem of dividing an array into subarrays to match specified bitwise AND values using dynamic programming.
Minimum Number of Operations to Satisfy Conditions
This problem asks to find the minimum number of operations on a 2D grid using state transition dynamic programming effic…
Find All Possible Stable Binary Arrays I
Find all stable binary arrays of a given number of 0's, 1's, and limit using dynamic programming and state transitions.
Find All Possible Stable Binary Arrays II
Compute the number of stable binary arrays using state transition dynamic programming with exact zero, one, and limit co…
Minimum Substring Partition of Equal Character Frequency
Partition a string into substrings with equal character frequencies using dynamic programming and state transitions.
Maximum Difference Score in a Grid
Maximize the score in a grid by making moves to the bottom or right, using state transition dynamic programming.
Find the Minimum Cost Array Permutation
Determine the lexicographically smallest permutation of nums that minimizes a cyclic score using state transition DP tec…
Find Number of Ways to Reach the K-th Stair
Determine the total number of ways to reach the k-th stair using a state transition dynamic programming approach with co…
Maximum Sum of Subsequence With Non-adjacent Elements
Compute the maximum sum of a subsequence where no two adjacent elements are selected after each array update efficiently…
Maximum Total Reward Using Operations I
Optimize the total reward by choosing operations on array indices using state transition dynamic programming techniques …
Maximum Total Reward Using Operations II
Maximize your total reward using dynamic programming with state transitions in this challenging problem involving array …
Minimum Operations to Make Binary Array Elements Equal to One II
Solve the Minimum Operations to Make Binary Array Elements Equal to One II using state transition dynamic programming ef…
Count the Number of Inversions
Count the number of valid permutations satisfying inversion constraints using state transition dynamic programming.
Maximize Total Cost of Alternating Subarrays
Maximize the total cost of alternating subarrays using dynamic programming to efficiently split an array into optimal su…
Find the Maximum Length of Valid Subsequence I
Find the longest valid subsequence in an array of integers using dynamic programming to handle different patterns of seq…
Find the Maximum Length of Valid Subsequence II
Determine the maximum length of a valid subsequence using state transition dynamic programming with careful modulo const…
Construct String with Minimum Cost
This problem asks you to construct a target string using given words at minimal cost using dynamic programming technique…
Minimum Cost for Cutting Cake I
In this problem, you need to minimize the cost of cutting a cake into 1x1 pieces using vertical and horizontal cuts.
Maximum Score From Grid Operations
Maximize your score by choosing the optimal sequence of column operations on a grid using dynamic programming transition…
Minimum Operations to Make Array Equal to Target
This problem requires calculating the minimum number of operations to transform one array into another using state trans…
Find the Count of Monotonic Pairs I
Compute the number of monotonic pairs in an integer array using state transition dynamic programming efficiently.
Find the Count of Monotonic Pairs II
This problem involves finding the count of monotonic pairs in an array using dynamic programming and combinatorics techn…
Maximum Value Sum by Placing Three Rooks I
Maximize the value sum by placing three rooks on a chessboard while ensuring they do not attack each other.
Maximum Value Sum by Placing Three Rooks II
Maximize the sum by placing three non-attacking rooks on a chessboard with dynamic programming.
Maximum Energy Boost From Two Drinks
Maximize energy boost from two drinks with a state transition dynamic programming approach.
Find the Largest Palindrome Divisible by K
Compute the largest n-digit integer divisible by k that forms a palindrome using state transition dynamic programming te…
Select Cells in Grid With Maximum Score
Optimize selection of grid cells using state transition dynamic programming to maximize total sum efficiently.
Maximum XOR Score Subarray Queries
Solve the Maximum XOR Score Subarray Queries problem using state transition dynamic programming for optimal subarray com…
Find the Maximum Sequence Value of Array
Determine the maximum value of a subsequence in an integer array using state transition dynamic programming and bit oper…
Maximum Multiplication Score
The problem requires selecting four indices from an array to maximize a dynamic score with a transition approach.
Minimum Number of Valid Strings to Form Target I
Use dynamic programming to split target into the fewest prefixes that match any word prefix, while ruling out dead posit…
Minimum Number of Valid Strings to Form Target II
Compute the minimum number of valid strings from an array needed to construct a given target string efficiently using dy…
Find the Lexicographically Smallest Valid Sequence
Determine the lexicographically smallest valid index sequence by using state transition dynamic programming over word1 a…
Find the Number of Possible Ways for an Event
Given n performers, x stages, and y scores, calculate the number of possible ways to assign performers and score bands.
Count The Number of Winning Sequences
Count The Number of Winning Sequences is a dynamic programming challenge involving state transitions based on Alice’s cr…
Maximum Points Tourist Can Earn
Calculate the maximum points a tourist can earn by choosing optimal city moves over k days using state transition DP.
Find the Original Typed String II
Calculate how many potential original strings Alice might have intended to type, considering her clumsy typing behavior.
Total Characters in String After Transformations I
Calculate the total number of characters in a string after repeated transformations using dynamic programming and freque…
Find the Number of Subsequences With Equal GCD
Count all pairs of non-empty subsequences in an integer array whose elements share the same greatest common divisor effi…
Total Characters in String After Transformations II
Calculate the length of a string after repeated transformations using state transition dynamic programming for large t v…
Count Number of Balanced Permutations
Determine how many distinct permutations of a digit string are balanced using state transition dynamic programming effic…
Count K-Reducible Numbers Less Than N
This problem challenges you to count the K-reducible numbers less than a given binary integer using dynamic programming.
Find the Maximum Number of Fruits Collected
Maximize the number of fruits collected by three children navigating a grid dungeon with dynamic programming.
Minimum Array Sum
Solve the Minimum Array Sum problem using dynamic programming by tracking states and operations to minimize the sum of a…
Minimum Time to Break Locks I
Solve the Minimum Time to Break Locks I problem using state transition dynamic programming to minimize the time to break…
Count Beautiful Splits in an Array
Learn to count all valid beautiful splits in an array using state transition dynamic programming efficiently and accurat…
Minimum Operations to Make Character Frequencies Equal
This Hard problem asks to transform a string so all character frequencies match using minimal deletions, leveraging dyna…
Count Paths With the Given XOR Value
Count the number of paths in a grid where the XOR of all values along the path equals a given number.
Longest Subsequence With Decreasing Adjacent Difference
Find the length of the longest subsequence with non-increasing absolute adjacent differences.
Maximize Subarray Sum After Removing All Occurrences of One Element
Maximize Subarray Sum After Removing All Occurrences of One Element involves finding the optimal subarray sum with one a…
Maximum Score of Non-overlapping Intervals
Maximize the score of up to 4 non-overlapping intervals, considering their weight and ensuring no overlap between chosen…
Maximum Amount of Money Robot Can Earn
Find the maximum amount of money a robot can collect while neutralizing robbers on its path in a grid.
Maximum and Minimum Sums of at Most Size K Subsequences
Find the sum of the maximum and minimum elements of subsequences with at most k elements, using dynamic programming.
Paint House IV
Solve the Paint House IV problem using state transition dynamic programming to minimize the painting costs while adherin…
Minimum Cost Good Caption
Solve Minimum Cost Good Caption with dynamic programming that builds minimum edit cost while enforcing character runs of…
Minimum Increments for Target Multiples in an Array
This problem involves incrementing elements of an array to make sure each target element has at least one multiple in th…
Count Substrings Divisible By Last Digit
Count the number of substrings in a string divisible by their last non-zero digit using dynamic programming.
Select K Disjoint Special Substrings
Determine if k non-overlapping special substrings exist in a string using dynamic programming and careful substring trac…
Length of Longest V-Shaped Diagonal Segment
Compute the maximum length of a V-shaped diagonal segment in a 2D integer matrix using state transition dynamic programm…
Find Minimum Cost to Remove Array Elements
Find the minimum cost to remove all elements from the array with dynamic programming.
Longest Palindromic Subsequence After at Most K Operations
Find the longest palindromic subsequence of a string after performing at most k operations to adjust letters.
Sum of K Subarrays With Length at Least M
Maximize the sum of k non-overlapping subarrays of at least length m using dynamic programming and prefix sums efficient…
Count Beautiful Numbers
Count Beautiful Numbers using state transition dynamic programming to efficiently calculate valid numbers in a given ran…
Minimum Cost to Divide Array Into Subarrays
Optimize array splits with dynamic programming to minimize costs for the Minimum Cost to Divide Array Into Subarrays pro…
Longest Palindrome After Substring Concatenation I
Compute the maximum palindrome length by concatenating substrings from two strings using state transition dynamic progra…
Longest Palindrome After Substring Concatenation II
Compute the longest palindrome by concatenating substrings from two strings using state transition dynamic programming e…
Count Numbers with Non-Decreasing Digits
Count all integers between l and r whose digits never decrease in base b using state transition dynamic programming effi…
Find X Value of Array I
Determine the x-value of an array using state transition dynamic programming to count valid prefix-suffix operations eff…
Concatenated Divisibility
Find the lexicographically smallest permutation of numbers whose concatenation is divisible by k using state transition …
Merge Operations for Minimum Travel Time
Minimize the total travel time by merging road signs, using dynamic programming to manage state transitions efficiently.
Find Sum of Array Product of Magical Sequences
Use state transition dynamic programming to count magical index sequences and accumulate weighted products without enume…
Maximum Weighted K-Edge Path
Determine the maximum sum of edge weights for a k-edge path in a DAG using state transition dynamic programming efficien…
Find Maximum Number of Non Intersecting Substrings
Determine the maximum number of non-overlapping substrings in a word, each at least four characters and matching start-e…
Lexicographically Smallest String After Adjacent Removals
Find the lexicographically smallest string by repeatedly removing adjacent characters optimally using dynamic programmin…
Best Time to Buy and Sell Stock V
Maximize profit from stock trades with at most k transactions using state transition dynamic programming for precise dec…
Count Partitions With Max-Min Difference at Most K
Count the number of valid ways to partition an array into contiguous segments where max-min difference is at most k.
Minimum Steps to Convert String with Operations
Transform word1 into word2 using minimal operations on substrings with a dynamic programming state transition approach.
Inverse Coin Change
Recover coin denominations from a numWays array using state transition dynamic programming to reconstruct valid sets eff…
Minimum Time to Transport All Individuals
Find the minimum time to transport individuals across a river with dynamic environmental conditions and boat capacity.
Partition Array to Minimize XOR
Partition an integer array into k subarrays to minimize the maximum XOR using state transition dynamic programming effic…
Minimum Cost Path with Alternating Directions II
This problem focuses on finding the minimum cost path with alternating directions in a grid using dynamic programming.
Longest Palindromic Path in Graph
Find the longest path in a graph that forms a palindrome using state transition dynamic programming and bitmask techniqu…
Number of Integers With Popcount-Depth Equal to K I
Calculate the number of integers in a given range with a specific popcount-depth using state transition dynamic programm…