Google Dynamic Programming Questions

397 dynamic programming problems asked at Google interviews

Easy (11)Medium (199)Hard (187)

Questions

TitleDifficulty
Trapping Rain WaterHard
Best Time to Buy and Sell StockEasy
Longest Palindromic SubstringMedium
Maximum SubarrayMedium
Climbing StairsEasy
Generate ParenthesesMedium
Pascal's TriangleEasy
Minimum Number of Increments on Subarrays to Form a Target ArrayHard
Jump GameMedium
Split Array Largest SumHard
House RobberMedium
Russian Doll EnvelopesHard
Longest Increasing SubsequenceMedium
Regular Expression MatchingHard
Maximal SquareMedium
Maximal RectangleHard
Unique PathsMedium
Maximum Product SubarrayMedium
Coin ChangeMedium
Binary Tree Maximum Path SumHard
Best Time to Buy and Sell Stock IIMedium
Jump Game IIMedium
Partition Equal Subset SumMedium
Fibonacci NumberEasy
Edit DistanceMedium
Sum of Subarray MinimumsMedium
Word BreakMedium
Palindrome PartitioningMedium
Wildcard MatchingHard
Target SumMedium
Burst BalloonsHard
Is SubsequenceEasy
Largest Divisible SubsetMedium
Longest Valid ParenthesesHard
Perfect SquaresMedium
Longest Common SubsequenceMedium
Longest Increasing Path in a MatrixHard
01 MatrixMedium
Coin Change IIMedium
Count Square Submatrices with All OnesMedium
House Robber IIMedium
Race CarHard
Odd Even JumpHard
Cheapest Flights Within K StopsMedium
Number of Matching SubsequencesMedium
Minimum Path SumMedium
Minimum Time to Finish the RaceHard
Min Cost Climbing StairsEasy
TriangleMedium
Domino and Tromino TilingMedium
Best Time to Buy and Sell Stock with CooldownMedium
Combination Sum IVMedium
Soup ServingsMedium
Sum of Distances in TreeHard
Champagne TowerMedium
Android Unlock PatternsMedium
Partition Array Into Two Arrays to Minimize Sum DifferenceHard
Shortest Path Visiting All NodesHard
Palindromic SubstringsMedium
Unique Paths IIMedium
Word Break IIHard
Count Numbers with Unique DigitsMedium
Predict the WinnerMedium
Minimum Falling Path SumMedium
Inverse Coin ChangeMedium
House Robber IIIMedium
Decode WaysMedium
New 21 GameMedium
Longest Arithmetic Subsequence of Given DifferenceMedium
Maximum Sum of 3 Non-Overlapping SubarraysHard
Valid Parenthesis StringMedium
Number of Digit OneHard
Non-overlapping IntervalsMedium
Best Time to Buy and Sell Stock IIIHard
Rotated DigitsMedium
Student Attendance Record IIHard
Painting a Grid With Three Different ColorsHard
Longest Palindromic SubsequenceMedium
Longest Arithmetic SubsequenceMedium
Sum of Good SubsequencesHard
Maximum Number of Points with CostMedium
Count Submatrices With All OnesMedium
Optimal Account BalancingHard
Longest Non-Decreasing Subarray After Replacing at Most One ElementMedium
Interleaving StringMedium
Pascal's Triangle IIEasy
Minimum Number of Flips to Make the Binary String AlternatingMedium
Minimum Cost to Cut a StickHard
Shortest Common SupersequenceHard
Longest Subarray of 1's After Deleting One ElementMedium
Filling Bookcase ShelvesMedium
Parallel Courses IIHard
Number of Ways to Build Sturdy Brick WallMedium
Ones and ZeroesMedium
Longest Mountain in ArrayMedium
Stone Game IIIHard
Delete Operation for Two StringsMedium
Maximum Sum Circular SubarrayMedium
Minimum Deletions to Make String BalancedMedium
Distinct SubsequencesHard
Best Time to Buy and Sell Stock IVHard
Find the Maximum Length of Valid Subsequence IMedium
Minimum Cost to Merge StonesHard
Longest Increasing Subsequence IIHard
Kth Ancestor of a Tree NodeHard
Cat and MouseHard
Number of Unique Good SubsequencesHard
Push DominoesMedium
The Earliest and Latest Rounds Where Players CompeteHard
Flip String to Monotone IncreasingMedium
Knight DialerMedium
Sort Integers by The Power ValueMedium
Minimum Distance to Type a Word Using Two FingersHard
Unique Binary Search Trees IIMedium
Longest String ChainMedium
Find the Maximum Sequence Value of ArrayHard
Dungeon GameHard
Counting BitsEasy
Number of Good Ways to Split a StringMedium
Find the Maximum Length of Valid Subsequence IIMedium
Integer ReplacementMedium
Cherry Pickup IIHard
Number of Ways of Cutting a PizzaHard
Jump Game VIIMedium
N-th Tribonacci NumberEasy
Minimum Cost For TicketsMedium
Frog JumpHard
Number of Ways to Arrive at DestinationMedium
Cat and Mouse IIHard
House Robber IVMedium
Two Best Non-Overlapping EventsMedium
Parallel Courses IIIHard
Paths in Matrix Whose Sum Is Divisible by KHard
All Possible Full Binary TreesMedium
Disconnect Path in a Binary Matrix by at Most One FlipMedium
Check if There is a Path With Equal Number of 0's And 1'sMedium
Video StitchingMedium
Sentence Screen FittingMedium
Paint FenceMedium
Minimum Number of Days to Eat N OrangesHard
Palindrome Partitioning IIHard
Solving Questions With BrainpowerMedium
Unique Binary Search TreesMedium
Best Sightseeing PairMedium
Longest Palindromic Subsequence After at Most K OperationsMedium
Stone GameMedium
Maximum Employees to Be Invited to a MeetingHard
Largest Color Value in a Directed GraphHard
Freedom TrailHard
Longest Binary Subsequence Less Than or Equal to KMedium
Max Consecutive Ones IIMedium
Minimum Window SubsequenceHard
String TransformationHard
Delete Columns to Make Sorted IIIHard
Maximum Number That Sum of the Prices Is Less Than or Equal to KMedium
Minimum Falling Path Sum IIHard
Pizza With 3n SlicesHard
Number of Restricted Paths From First to Last NodeMedium
Guess Number Higher or Lower IIMedium
Count Fertile Pyramids in a LandHard
Beautiful ArrangementMedium
Largest Sum of AveragesMedium
Numbers With Repeated DigitsHard
Maximum Non Negative Product in a MatrixMedium
Divisor GameEasy
Number of Ways to Reorder Array to Get Same BSTHard
Maximum AND Sum of ArrayHard
Super Egg DropHard
Maximum Value of K Coins From PilesHard
Minimum Time to Remove All Cars Containing Illegal GoodsHard
Number of Beautiful PartitionsHard
Longest Line of Consecutive One in MatrixMedium
Number of Ways to Stay in the Same Place After Some StepsHard
Find Two Non-overlapping Sub-arrays Each With Target SumMedium
Minimum Cost to Connect Two Groups of PointsHard
Distribute Repeating IntegersHard
Maximum Score from Performing Multiplication OperationsHard
Maximum Number of Groups Getting Fresh DonutsHard
Longest Chunked Palindrome DecompositionHard
Profitable SchemesHard
Super Ugly NumberMedium
Shopping OffersMedium
Last Stone Weight IIMedium
Partition Array for Maximum SumMedium
Number of Longest Increasing SubsequenceMedium
Integer BreakMedium
Maximum Profit in Job SchedulingHard
Scramble StringHard
Number of Ways to Form a Target String Given a DictionaryHard
Different Ways to Add ParenthesesMedium
Find the City With the Smallest Number of Neighbors at a Threshold DistanceMedium
Find the Count of Monotonic Pairs IHard
Minimize the Maximum Difference of PairsMedium
4 Keys KeyboardMedium
Minimum Flips in Binary Tree to Get ResultHard
Bomb EnemyMedium
Maximize Total Cost of Alternating SubarraysMedium
Closest Dessert CostMedium
Maximize Consecutive Elements in an Array After ModificationHard
Minimum White Tiles After Covering With CarpetsHard
Flip Game IIMedium
Check if There Is a Valid Parentheses String PathHard
Encode String with Shortest LengthHard
Maximum Vacation DaysHard
Coin PathHard
Campus Bikes IIMedium
Minimum Increment Operations to Make Array BeautifulMedium
Shortest Distance to Target ColorMedium
Maximum Score After Applying Operations on a TreeMedium
Minimum Sum of Values by Dividing ArrayHard
Minimum Path Cost in a GridMedium
Form Largest Integer With Digits That Add up to TargetHard
The Most Similar Path in a GraphHard
Count Ways to Distribute CandiesHard
Number of Ways to Rearrange Sticks With K Sticks VisibleHard
Minimum Cost to Change the Final Value of ExpressionHard
Minimum Skips to Arrive at Meeting On TimeHard
Number of Stable SubsequencesHard
Maximum Sum BST in Binary TreeHard
Partition to K Equal Sum SubsetsMedium
Maximum Number of Events That Can Be Attended IIHard
Find the Original Typed String IIHard
Delete and EarnMedium
Minimum Number of Refueling StopsHard
Bitwise ORs of SubarraysMedium
Find the Shortest SuperstringHard
Maximum Absolute Sum of Any SubarrayMedium
Number of People Aware of a SecretMedium
Remove BoxesHard
Cherry PickupHard
Best Time to Buy and Sell Stock with Transaction FeeMedium
2 Keys KeyboardMedium
Ways to Express an Integer as Sum of PowersMedium
Minimum Increments to Equalize Leaf PathsMedium
Ugly Number IIMedium
Minimum Number of Taps to Open to Water a GardenHard
Best Time to Buy and Sell Stock VMedium
Twisted Mirror Path CountMedium
Number of ZigZag Arrays IHard
Maximum Path Score in a GridMedium
Find All Possible Stable Binary Arrays IMedium
Arithmetic SlicesMedium
Extra Characters in a StringMedium
Count Number of Balanced PermutationsHard
Count the Number of Square-Free SubsetsMedium
Count the Number of Powerful IntegersHard
Paint House IIIHard
Maximum Length of Repeated SubarrayMedium
Find the Minimum Cost Array PermutationHard
Maximum Score From Grid OperationsHard
Rotate FunctionMedium
Jump Game VHard
Max Dot Product of Two SubsequencesHard
Trionic Array IIHard
Painting the WallsHard
Count Number of TeamsMedium
Number of Sub-arrays With Odd SumMedium
Count the Number of Ideal ArraysHard
Maximum Students Taking ExamHard
Get the Maximum ScoreHard
Number of Ways to Assign Edge Weights IIHard
Jump Game IXMedium
Tallest BillboardHard
Number of Dice Rolls With Target SumMedium
Jump Game VIMedium
Stone Game IIMedium
Minimum Number of Removals to Make Mountain ArrayHard
Total Characters in String After Transformations IIHard
Maximum Height by Stacking CuboidsHard
Taking Maximum Energy From the Mystic DungeonMedium
Length of Longest Fibonacci SubsequenceMedium
Minimum Insertion Steps to Make a String PalindromeHard
Maximize Subarray Sum After Removing All Occurrences of One ElementHard
Maximum Frequency After Subarray OperationMedium
Minimum Cost Tree From Leaf ValuesMedium
Count Partitions With Max-Min Difference at Most KMedium
Greatest Sum Divisible by ThreeMedium
Knight Probability in ChessboardMedium
Distinct Subsequences IIHard
Minimum Total Distance TraveledHard
Maximum Sum of Subsequence With Non-adjacent ElementsHard
Minimum Score Triangulation of PolygonMedium
Can I WinMedium
Number of Ways to Paint N × 3 GridHard
Minimum ASCII Delete Sum for Two StringsMedium
Maximum Total Damage With Spell CastingMedium
Number of Smooth Descent Periods of a StockMedium
Total Waviness of Numbers in Range IIHard
Number of ZigZag Arrays IIHard
Maximize Cyclic Partition ScoreHard
Total Waviness of Numbers in Range IMedium
Minimum Cost Path with TeleportationsHard
Arithmetic Slices II - SubsequenceHard
Constrained Subsequence SumHard
Binary Tree CamerasHard
K Inverse Pairs ArrayHard
Build Array Where You Can Find The Maximum Exactly K ComparisonsHard
Maximum Repeating SubstringEasy
Find Weighted Median Node in TreeHard
Number of Squareful ArraysHard
Matchsticks to SquareMedium
Strange PrinterHard
Find Good Days to Rob the BankMedium
Minimum Difference in Sums After Removal of ElementsHard
Find the String with LCPHard
Minimum Cost to Reach Destination in TimeHard
Subsequence Sum After Capping ElementsMedium
Longest Turbulent SubarrayMedium
Number of Ways to Reach a Position After Exactly k StepsMedium
Minimum Additions to Make Valid StringMedium
Find the Maximum Sum of Node ValuesHard
Maximum Score Words Formed by LettersHard
Count Palindromic SubsequencesHard
Maximum Subarray Sum with One DeletionMedium
Make Array Non-decreasing or Non-increasingHard
Sliding PuzzleHard
Maximum Number of Moves in a GridMedium
Unique Substrings in Wraparound StringMedium
Uncrossed LinesMedium
Total Appeal of A StringHard
Find the Maximum Number of Fruits CollectedHard
Length of Longest V-Shaped Diagonal SegmentHard
Longest Non-decreasing Subarray From Two ArraysMedium
Total Characters in String After Transformations IMedium
Stone Game VIIMedium
Minimum One Bit Operations to Make Integers ZeroHard
Maximum Product of the Length of Two Palindromic SubsequencesMedium
Reducing DishesHard
Allocate MailboxesHard
Count Distinct Integers After Removing ZerosMedium
Maximum Profit from Trading Stocks with DiscountsHard
Maximum Length of Pair ChainMedium
Egg Drop With 2 Eggs and N FloorsMedium
Count Ways To Build Good StringsMedium
Closest Subsequence SumHard
Find Minimum Time to Finish All JobsHard
Make the XOR of All Segments Equal to ZeroHard
Count The RepetitionsHard
Minimum Difficulty of a Job ScheduleHard
Path Existence Queries in a Graph IIHard
Maximum Amount of Money Robot Can EarnMedium
Best Team With No ConflictsMedium
Count Sequences to KHard
Stickers to Spell WordHard
Count All Valid Pickup and Delivery OptionsHard
Minimum Sideway JumpsMedium
Check if There is a Valid Partition For The ArrayMedium
Poor PigsHard
Paint HouseMedium
Find Maximum Non-decreasing Array LengthHard
Minimum Operations to Make Array Equal to TargetHard
Find the Largest Palindrome Divisible by KHard
Maximum XOR Score Subarray QueriesHard
Find All Good StringsHard
Longest Square Streak in an ArrayMedium
Stone Game VHard
Find Maximum Removals From Source StringMedium
Minimum Operations to Make Character Frequencies EqualHard
Longest Subsequence With Decreasing Adjacent DifferenceMedium
Zero Array Transformation IVMedium
Merge Operations for Minimum Travel TimeHard
Minimum Moves to Spread Stones Over GridMedium
Non-negative Integers without Consecutive OnesHard
String Compression IIHard
Longest Repeating SubstringMedium
Count Different Palindromic SubsequencesHard
Longest Palindrome After Substring Concatenation IMedium
Minimum Cost to Convert String IIHard
Minimum Operations to Reduce an Integer to 0Medium
Minimum Array SumMedium
Maximum Alternating Subsequence SumMedium
Count The Number of Winning SequencesHard
Longest Palindrome After Substring Concatenation IIHard
Split Array With Same AverageHard
Count Substrings Divisible By Last DigitHard
Find Minimum Cost to Remove Array ElementsMedium
Count Number of Ways to Place HousesMedium
Binary Trees With FactorsMedium
Zuma GameHard
Count the Number of InversionsHard
The Number of Beautiful SubsetsMedium
Restore The ArrayHard
As Far from Land as PossibleMedium
K-Concatenation Maximum SumMedium
Count Sorted Vowel StringsMedium
Partition Array to Minimize XORMedium
Find the Number of Subsequences With Equal GCDHard
Count Beautiful NumbersHard
Numbers At Most N Given Digit SetHard
Minimum XOR Path in a GridMedium
Minimum Edge Reversals So Every Node Is ReachableHard
Count Stepping Numbers in RangeHard
Find the Sum of the Power of All SubsequencesHard
Minimum Swaps To Make Sequences IncreasingHard
Longest Palindromic Path in GraphHard
Minimize the Difference Between Target and Chosen ElementsMedium
Dice Roll SimulationHard

Showing 397 questions