Most Important Dynamic Programming Questions for Google Interviews
Dynamic Programming (DP) is one of the most challenging yet important topics in Google coding interviews. It is used to solve complex problems by breaking them into smaller overlapping subproblems and optimizing repeated computations.
In this guide, you'll find the most asked Dynamic Programming LeetCode questions in Google interviews, along with their difficulty and frequency.
| Sl.No | Question | Difficulty | Frequency | LeetCode Link |
|---|
| 1 | Trapping Rain Water | HARD | 85.90% | Solve |
| 2 | Longest Palindromic Substring | MEDIUM | 77.10% | Solve |
| 3 | Best Time to Buy and Sell Stock | EASY | 73.40% | Solve |
| 4 | Maximum Subarray | MEDIUM | 71.10% | Solve |
| 5 | Climbing Stairs | EASY | 69.80% | Solve |
| 6 | Jump Game | MEDIUM | 69.80% | Solve |
| 7 | Generate Parentheses | MEDIUM | 68.60% | Solve |
| 8 | Minimum Number of Increments on Subarrays to Form a Target Array | HARD | 62.50% | Solve |
| 9 | Word Break | MEDIUM | 60.60% | Solve |
| 10 | Jump Game II | MEDIUM | 59.10% | Solve |
| 11 | Unique Paths | MEDIUM | 56.90% | Solve |
| 12 | Regular Expression Matching | HARD | 56.10% | Solve |
| 13 | Pascal's Triangle | EASY | 55.40% | Solve |
| 14 | Word Break II | HARD | 53.30% | Solve |
| 15 | Odd Even Jump | HARD | 50.00% | Solve |
| 16 | Longest Valid Parentheses | HARD | 48.70% | Solve |
| 17 | String Transformation | HARD | 46.20% | Solve |
| 18 | Edit Distance | MEDIUM | 45.70% | Solve |
| 19 | Maximum Product Subarray | MEDIUM | 45.50% | Solve |
| 20 | Decode Ways | MEDIUM | 45.30% | Solve |
| 21 | Minimum Path Sum | MEDIUM | 44.30% | Solve |
| 22 | Minimum Number of Taps to Open to Water a Garden | HARD | 41.70% | Solve |
| 23 | Filling Bookcase Shelves | MEDIUM | 41.70% | Solve |
| 24 | Wildcard Matching | HARD | 41.60% | Solve |
| 25 | Best Time to Buy and Sell Stock II | MEDIUM | 38.90% | Solve |
| 26 | Partition Array Into Two Arrays to Minimize Sum Difference | HARD | 37.50% | Solve |
| 27 | Sum of Distances in Tree | HARD | 37.50% | Solve |
| 28 | Count Numbers with Unique Digits | MEDIUM | 37.50% | Solve |
| 29 | Student Attendance Record II | HARD | 37.50% | Solve |
| 30 | Maximum Number of Points with Cost | MEDIUM | 37.50% | Solve |
| 31 | Sentence Screen Fitting | MEDIUM | 37.50% | Solve |
| 32 | Maximum Sum of 3 Non-Overlapping Subarrays | HARD | 37.50% | Solve |
| 33 | Minimum Time to Finish the Race | HARD | 37.50% | Solve |
| 34 | Count Vowels Permutation | HARD | 37.10% | Solve |
| 35 | Maximal Rectangle | HARD | 36.10% | Solve |
| 36 | Unique Paths II | MEDIUM | 35.30% | Solve |
| 37 | Unique Binary Search Trees II | MEDIUM | 35.30% | Solve |
| 38 | Best Time to Buy and Sell Stock with Cooldown | MEDIUM | 33.20% | Solve |
| 39 | Binary Tree Maximum Path Sum | HARD | 30.70% | Solve |
| 40 | Number of Digit One | HARD | 30.60% | Solve |
| 41 | Interleaving String | MEDIUM | 28.10% | Solve |
| 42 | Best Time to Buy and Sell Stock IV | HARD | 27.50% | Solve |
| 43 | Unique Binary Search Trees | MEDIUM | 26.80% | Solve |
| 44 | Paint Fence | MEDIUM | 25.10% | Solve |
| 45 | Minimum Increment Operations to Make Array Beautiful | MEDIUM | 25.00% | Solve |
| 46 | Minimum Cost to Connect Two Groups of Points | HARD | 25.00% | Solve |
| 47 | Form Largest Integer With Digits That Add up to Target | HARD | 25.00% | Solve |
| 48 | Count Fertile Pyramids in a Land | HARD | 25.00% | Solve |
| 49 | Delete Columns to Make Sorted III | HARD | 25.00% | Solve |
| 50 | Maximize Consecutive Elements in an Array After Modification | HARD | 25.00% | Solve |
Why Dynamic Programming is Critical for Google
Google frequently tests your ability to:
- Identify overlapping subproblems
- Optimize recursive solutions using memoization
- Convert recursion into tabulation (bottom-up DP)
- Solve optimization problems efficiently
DP is often used in:
- Optimization problems
- Subsequence and substring problems
- Grid-based problems
- Decision-making problems
Must-Know DP Patterns
To crack Google interviews, focus on these patterns:
- 0/1 Knapsack
- Longest Common Subsequence (LCS)
- Longest Increasing Subsequence (LIS)
- DP on Strings
- DP on Grids
- DP with Bitmasking (advanced)
How to Prepare Effectively
Follow this structured approach:
- Start with recursion (understand problem structure)
- Add memoization (top-down DP)
- Convert to tabulation (bottom-up DP)
- Optimize space complexity
Track your progress here:
Google LeetCode Interview Questions Tracker
Strengthen Your Google Preparation
Dynamic Programming is often combined with other DSA topics. Make sure you also cover:
Explore Complete Google Question Set
If you are serious about Google interviews:
Google LeetCode Questions (247+ Problems with Frequency)
Practice Questions from Other Companies
You can also explore:
Final Thoughts
Dynamic Programming is often considered difficult, but it becomes manageable once you understand patterns and practice consistently.
If you master DP, you unlock the ability to solve some of the most complex problems asked in Google interviews.
Pro Tip: Combine DP with Binary Search + Greedy + Graphs to handle advanced interview questions.