Dynamic Programming

  • Last Updated : 02 Aug, 2022

Data Structure and Algorithms Course
Practice Problems on Dynamic Programming
Recent Articles on Dynamic Programming

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.

dynamic-programming

Topics:

Basic Concepts :

  1. Tabulation vs Memoizatation
  2. Optimal Substructure Property
  3. Overlapping Subproblems Property
  4. How to solve a Dynamic Programming Problem ?

DSA-Self-Paced

Advanced Concepts :

  1. Bitmasking and Dynamic Programming | Set 1
  2. Bitmasking and Dynamic Programming | Set-2 (TSP)
  3. Digit DP | Introduction

Basic Problems :

  1. Ugly numbers
  2. Fibonacci numbers
  3. nth Catalan Number
  4. Bell Numbers (Number of ways to Partition a Set)
  5. Binomial Coefficient
  6. Permutation Coefficient
  7. Tiling Problem
  8. Gold Mine Problem
  9. Coin change problem
  10. Friends Pairing Problem
  11. Subset Sum Problem
  12. Subset Sum Problem in O(sum) space
  13. Subset with sum divisible by m
  14. Largest divisible pairs subset
  15. Perfect Sum Problem (Print all subsets with given sum)
  16. Compute nCr % p
  17. Choice of area
  18. Cutting a Rod
  19. Tiling with Dominoes
  20. Painting Fence Algorithm
  21. Newman–Shanks–Williams prime
  22. Assembly line scheduling
  23. Golomb sequence
  24. Moser-de Bruijn Sequence
  25. Newman-Conway Sequence
  26. Find maximum length Snake sequence
  27. Print n terms of Newman-Conway Sequence
  28. Print Fibonacci sequence using 2 variables
  29. Print Fibonacci Series in reverse order
  30. Count even length binary sequences with same sum of first and second half bits
  31. Sequences of given length where every element is more than or equal to twice of previous
  32. Longest Common Subsequence
  33. Longest Repeated Subsequence
  34. Longest Increasing Subsequence
  35. A Space Optimized Solution of LCS
  36. LCS (Longest Common Subsequence) of three strings
  37. Maximum sum Bi-tonic Sub-sequence
  38. Maximum Sum Increasing Subsequence
  39. Maximum product of an increasing subsequence
  40. Count all subsequences having product less than K
  41. Maximum subsequence sum such that no three are consecutive
  42. Longest subsequence such that difference between adjacents is one
  43. Maximum length subsequence with difference between adjacent elements as either 0 or 1
  44. Maximum sum increasing subsequence from a prefix and a given element after prefix is must
  45. Maximum Length Chain of Pairs
  46. Print Maximum Length Chain of Pairs
  47. Path with maximum average value
  48. Maximum games played by winner
  49. Maximum path sum in a triangle
  50. Minimum Sum Path in a Triangle
  51. Maximum sum of a path in a Right Number Triangle
  52. Size of The Subarray With Maximum Sum
  53. Maximum sum of pairs with specific difference
  54. Maximum size square sub-matrix with all 1s
  55. Maximum number of segments of lengths a, b and c
  56. Recursively break a number in 3 parts to get maximum sum
  57. Maximum value with the choice of either dividing or considering as it is
  58. Maximum weight path ending at any element of last row in a matrix
  59. Maximum sum in a 2 x n grid such that no two elements are adjacent
  60. Maximum difference of zeros and ones in binary string | Set 2 (O(n) time)
  61. Maximum path sum for each position with jumps under divisibility condition
  62. Maximize the sum of selected numbers from an array to make it empty
  63. Maximum subarray sum in an array created after repeated concatenation
  64. Maximum path sum that starting with any cell of 0-th row and ending with any cell of (N-1)-th row
  65. Min Cost Path
  66. Minimum number of jumps to reach end
  67. Minimum cost to fill given weight in a bag
  68. Minimum sum of multiplications of n numbers
  69. Minimum removals from array to make max – min <= K
  70. Minimum steps to minimize n as per given condition
  71. Minimum number of edits ( operations ) require to convert string 1 to string 2
  72. Minimum time to write characters using insert, delete and copy operation
  73. Longest Common Substring
  74. Longest Common Substring (Space optimized DP solution)
  75. Sum of all substrings of a string representing a number | Set 1
  76. Find number of endless points
  77. Find n-th element from Stern’s Diatomic Series
  78. Find maximum possible stolen value from houses
  79. Find number of solutions of a linear equation of n variables
  80. Count number of ways to reach a given score in a game
  81. Count ways to reach the nth stair using step 1, 2 or 3
  82. Count of different ways to express N as the sum of 1, 3 and 4
  83. Count ways to build street under given constraints
  84. Count Balanced Binary Trees of Height h
  85. Counting pairs when a person can form pair with at most one
  86. Counts paths from a point to reach Origin
  87. Count number of ways to cover a distance
  88. Count of arrays having consecutive element with different values
  89. Count ways to divide circle using N non-intersecting chords
  90. Count the number of ways to tile the floor of size n x m using 1 x m size tiles
  91. Count all possible paths from top left to bottom right of a mXn matrix
  92. Count number of ways to fill a “n x 4” grid using “1 x 4” tiles
  93. Largest Sum Contiguous Subarray
  94. Smallest sum contiguous subarray
  95. Size of array after repeated deletion of LIS
  96. Remove array end element to maximize the sum of product
  97. Convert to Strictly increasing array with minimum changes
  98. Longest alternating (positive and negative) subarray starting at every index
  99. Ways to sum to N using array elements with repetition allowed
  100. Unique paths in a Grid with Obstacles
  101. Number of n-digits non-decreasing integers
  102. Number of ways to arrange N items under given constraints
  103. Probability of reaching a point with 2 or 3 steps at a time
  104. Value of continuous floor function : F(x) = F(floor(x/2)) + x
  105. Number of decimal numbers of length k, that are strict monotone
  106. Different ways to sum n using numbers greater than or equal to m

Intermediate Problems :

  1. Lobb Number
  2. Eulerian Number
  3. Delannoy Number
  4. Entringer Number
  5. Rencontres Number
  6. Jacobsthal and Jacobsthal-Lucas numbers
  7. Super Ugly Number (Number whose prime factors are in given set)
  8. Floyd Warshall Algorithm
  9. Bellman–Ford Algorithm
  10. 0-1 Knapsack Problem
  11. Printing Items in 0/1 Knapsack
  12. Unbounded Knapsack (Repetition of items allowed)
  13. Temple Offerings
  14. Egg Dropping Puzzle
  15. Dice Throw Problem
  16. Word Break Problem
  17. Vertex Cover Problem
  18. Tile Stacking Problem
  19. Box-Stacking Problem
  20. Highway Billboard Problem
  21. Largest Independent Set Problem
  22. Partition Problem
  23. Print equal sum sets of array (Partition problem) | Set 1
  24. Print equal sum sets of array (Partition Problem) | Set 2
  25. High-effort vs. Low-effort Tasks Problem
  26. Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming)
  27. Longest Bitonic Subsequence
  28. Printing Longest Bitonic Subsequence
  29. Longest Palindromic Subsequence
  30. Print Longest Palindromic Subsequence
  31. Longest palindrome subsequence with O(n) space
  32. Count All Palindromic Subsequence in a given String
  33. Longest Palindromic Substring | Set 1
  34. Count All Palindrome Sub-Strings in a String | Set 1
  35. Number of palindromic subsequences of length k
  36. Count of Palindromic substrings in an Index range
  37. Shortest Common Supersequence
  38. Maximum sum alternating subsequence
  39. Longest alternating subsequence
  40. Shortest Uncommon Subsequence
  41. Longest Repeating Subsequence
  42. Count Distinct Subsequences
  43. Count distinct occurrences as a subsequence
  44. Longest Common Increasing Subsequence (LCS + LIS)
  45. Variations of LIS
  46. LCS formed by consecutive segments of at least length K
  47. Printing Maximum Sum Increasing Subsequence
  48. Longest Increasing Odd Even Subsequence
  49. Count number of increasing subsequences of size k
  50. Printing longest Increasing consecutive subsequence
  51. Construction of Longest Increasing Subsequence using Dynamic Programming
  52. Longest Zig-Zag Subsequence
  53. Largest sum Zigzag sequence in a matrix
  54. Find all distinct subset (or subsequence) sums of an array
  55. Print all longest common sub-sequences in lexicographical order
  56. Printing Longest Common Subsequence | Set 2 (Printing All)
  57. Length of Longest Balanced Subsequence
  58. Non-decreasing subsequence of size k with minimum sum
  59. Longest Common Subsequence with at most k changes allowed
  60. Weighted job scheduling
  61. Weighted Job Scheduling | Set 2 (Using LIS)
  62. Weighted Job Scheduling in O(n Log n) time
  63. Number of paths with exactly k coins
  64. Minimum number of coins that make a given value
  65. Collect maximum coins before hitting a dead end
  66. Coin game winner where every player has three choices
  67. Probability of getting at least K heads in N tosses of Coins
  68. Count all increasing subsequences
  69. Count number of paths with at-most k turns
  70. Count possible ways to construct buildings
  71. Count number of ways to jump to reach end
  72. Count number of ways to reach destination in a Maze
  73. Count all triplets whose sum is equal to a perfect cube
  74. Count number of binary strings without consecutive 1’s
  75. Count number of subsets having a particular XOR value
  76. Count Possible Decodings of a given Digit Sequence
  77. Count number of ways to partition a set into k subsets
  78. Count of n digit numbers whose sum of digits equals to given sum
  79. Count ways to assign unique cap to every person
  80. Count binary strings with k times appearing adjacent two set bits
  81. Count of strings that can be formed using a, b and c under given constraints
  82. Count digit groupings of a number with given constraints
  83. Count all possible walks from a source to a destination with exactly k edges
  84. Count Derangements (Permutation such that no element appears in its original position)
  85. Count total number of N digit numbers such that the difference between sum of even and odd digits is 1
  86. Maximum Product Cutting
  87. Maximum profit from sale of wines
  88. Maximum size subset with given sum
  89. Maximum difference of zeros and ones in binary string
  90. Maximum and Minimum Values of an Algebraic Expression
  91. Maximum average sum partition of an array
  92. Maximize array elements upto given number
  93. Maximum subarray sum in O(n) using prefix sum
  94. Maximum sum subarray removing at most one element
  95. K maximum sums of non-overlapping contiguous sub-arrays
  96. Maximum Product Subarray | Added negative product case
  97. Find maximum sum array of length less than or equal to m
  98. Find Maximum dot product of two arrays with insertion of 0’s
  99. Choose maximum weight with given weight and value ratio
  100. Maximum sum subsequence with at-least k distant elements
  101. Maximum profit by buying and selling a share at most twice
  102. Maximum sum path in a matrix from top to bottom
  103. Maximum decimal value path in a binary matrix
  104. Finding the maximum square sub-matrix with all equal elements
  105. Maximum points collected by two persons allowed to meet once
  106. Maximum number of trailing zeros in the product of the subsets of size k
  107. Minimum Sum Path In 3-D Array
  108. Minimum insertions to sort an array
  109. Minimum sum submatrix in a given 2D array
  110. Minimum Initial Points to Reach Destination
  111. Minimum Cost To Make Two Strings Identical
  112. Paper Cut into Minimum Number of Squares | Set 2
  113. Minimum and Maximum values of an expression with * and +
  114. Minimum insertions to form a palindrome
  115. Minimum number of deletions to make a string palindrome
  116. Minimum number of deletions to make a string palindrome | Set 2
  117. Minimum jumps to reach last building in a matrix
  118. Sub-tree with minimum color difference in a 2-coloured tree
  119. Minimum number of deletions to make a sorted sequence
  120. Minimum number of squares whose sum equals to given number n
  121. Remove minimum elements from either side such that 2*min becomes more than max
  122. Minimal moves to form a string by adding characters or appending string itself
  123. Minimum steps to delete a string after repeated deletion of palindrome substrings
  124. Clustering/Partitioning an array such that sum of square differences is minimum
  125. Minimum sum subsequence such that at least one of every four consecutive elements is picked
  126. Minimum cost to make Longest Common Subsequence of length k
  127. Minimum cost to make two strings identical by deleting the digits
  128. Minimum time to finish tasks without skipping two consecutive
  129. Minimum cells required to reach destination with jumps equal to cell values
  130. Minimum number of deletions and insertions to transform one string into another
  131. Find minimum adjustment cost of an array
  132. Find if string is K-Palindrome or not | Set 1
  133. Find if string is K-Palindrome or not | Set 2
  134. Find Jobs involved in Weighted Job Scheduling
  135. Find the Longest Increasing Subsequence in Circular manner
  136. Find the longest path in a matrix with given constraints
  137. Find the minimum cost to reach destination using a train
  138. Find minimum sum such that one of every three consecutive elements is taken
  139. Find number of times a string occurs as a subsequence in given string
  140. Find length of the longest consecutive path from a given starting character
  141. Find length of longest subsequence of one string which is substring of another string
  142. Find longest bitonic sequence such that increasing and decreasing parts are from two different arrays
  143. Wildcard Pattern Matching
  144. WildCard pattern matching having three symbols ( * , + , ? )
  145. Dynamic Programming | Wildcard Pattern Matching | Linear Time and Constant Space
  146. Check if any valid sequence is divisible by M
  147. Check for possible path in 2D matrix
  148. Check if possible to cross the matrix with given power
  149. Check if it is possible to transform one string to another
  150. Given a large number, check if a subsequence of digits is divisible by 8
  151. Hosoya’s Triangle
  152. Optimal Strategy for a game
  153. Optimal Binary Search Tree
  154. Number of permutation with K inversions
  155. Largest divisible pairs subset
  156. Sum of average of all subsets
  157. Compute sum of digits in all numbers from 1 to n
  158. Total number of non-decreasing numbers with n digits
  159. Non-crossing lines to connect points in a circle
  160. Dynamic Programming | Building Bridges
  161. Longest Increasing Path in Matrix
  162. Prefix Sum of Matrix (Or 2D Array)
  163. Multistage Graph (Shortest Path)
  164. Number of n digit stepping numbers
  165. Number of substrings divisible by 8 but not by 3
  166. Number of ordered pairs such that (Ai & Aj) = 0
  167. Number of ways to form a heap with n distinct integers
  168. Ways to write n as sum of two or more positive integers
  169. Modify array to maximize sum of adjacent differences
  170. Sum of products of all combination taken (1 to n) at a time
  171. Maximize the binary matrix by filpping submatrix once
  172. Length of the longest substring without repeating characters
  173. Longest Even Length Substring such that Sum of First and Second Half is same
  174. Shortest path with exactly k edges in a directed and weighted graph
  175. Ways to arrange Balls such that adjacent balls are of different types
  176. Ways of transforming one string to other by removing 0 or more characters
  177. Balanced expressions such that given positions have opening brackets
  178. Longest alternating sub-array starting from every index in a Binary Array
  179. Partition a set into two subsets such that the difference of subset sums is minimum
  180. Pyramid form (increasing then decreasing) consecutive array using reduce operations

Hard Problems :

  1. Palindrome Partitioning
  2. Word Wrap Problem
  3. Mobile Numeric Keypad Problem
  4. The painter’s partition problem
  5. Boolean Parenthesization Problem
  6. Program for Bridge and Torch problem
  7. A Space Optimized DP solution for 0-1 Knapsack Problem
  8. Matrix Chain Multiplication
  9. Printing brackets in Matrix Chain Multiplication Problem
  10. Number of palindromic paths in a matrix
  11. Largest rectangular sub-matrix whose sum is 0
  12. Largest rectangular sub-matrix having sum divisible by k
  13. Largest area rectangular sub-matrix with equal number of 1’s and 0’s
  14. Maximum sum bitonic subarray
  15. Maximum sum rectangle in a 2D matrix
  16. Maximum Subarray Sum Excluding Certain Elements
  17. Maximum weight transformation of a given string
  18. Collect maximum points in a grid using two traversals
  19. K maximum sums of overlapping contiguous sub-arrays
  20. How to print maximum number of A’s using given four keys
  21. Maximize arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l
  22. Maximum profit by buying and selling a share at most k times
  23. Maximum points from top left of matrix to bottom right and return back
  24. Check whether row or column swaps produce maximum size binary sub-matrix with all 1s
  25. Minimum Cost Polygon Triangulation
  26. Minimum cost to sort strings using reversal operations of different costs
  27. Find minimum possible size of array with given rules for removing elements
  28. Minimum number of elements which are not part of Increasing or decreasing subsequence in array
  29. Count ways to increase LCS length of two strings by one
  30. Count of AP (Arithmetic Progression) Subsequences in an array
  31. Count of arrays in which all adjacent elements are such that one of them divide the another
  32. Number of NGEs to the right
  33. Longest Arithmetic Progression
  34. Longest Geometric Progression
  35. Dynamic Programming on Trees | Set-1
  36. Dynamic Programming on Trees | Set-2
  37. All ways to add parenthesis for evaluation
  38. Shortest possible combination of two strings
  39. Check if all people can vote on two machines
  40. Find if a string is interleaved of two other strings
  41. Longest repeating and non-overlapping substring
  42. Probability of Knight to remain in the chessboard
  43. Number of subsequences of the form a^i b^j c^k
  44. Number of subsequences in a string divisible by n
  45. Printing Shortest Common Supersequence
  46. Smallest length string with repeated replacement of two distinct adjacent
  47. Number of ways to insert a character to increase the LCS by one
  48. Traversal of tree with k jumps allowed between nodes of same height
  49. Find all combinations of k-bit numbers with n bits set where 1 <= n <= k in sorted order

Quick Links :

  1. Top 20 Dynamic Programming Interview Questions
  2. ‘Practice Problems’ on Dynamic Programming
  3. ‘Quiz’ on Dynamic Programming

GeeksforGeeks Courses:

1. Language Foundation Courses [C++ / JAVA / Python ]
Learn any programming language from scratch and understand all its fundamentals concepts for a strong programming foundation in the easiest possible manner with help of GeeksforGeeks Language Foundation Courses – Java Foundation | Python Foundation | C++ Foundation

2. Complete Interview Preparation
Get fulfilled all your interview preparation needs at a single place with the Complete Interview Preparation Course that provides you all the required stuff to prepare for any product-based, service-based, or start-up company at the most affordable prices.

3. DSA Self Paced
Start learning Data Structures and Algorithms to prepare for the interviews of top IT giants like Microsoft, Amazon, Adobe, etc. with DSA Self-Paced Course where you will get to learn and master DSA from basic to advanced level and that too at your own pace and convenience.

4. Company Specific Courses – Amazon & Microsoft
Crack the interview of any product-based giant company by specifically preparing with the questions that these companies usually ask in their coding interview round. Refer GeeksforGeeks Company Specific Courses: Amazon SDE Test Series, etc.

If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.


My Personal Notes arrow_drop_up


Writing code in comment? Please use ide.geeksforgeeks.org, generate link and share the link here.