Google Dynamic Programming Questions

362 dynamic programming problems asked at Google interviews

Easy (11)Medium (184)Hard (167)

Questions

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

Showing 362 questions