OpenSource Internship opportunity by OpenGenus for programmers. Apply now.
This is the List of 100+ Dynamic Programming (DP) Problems along with different types of DP problems such as Mathematical DP, Combination DP, String DP, Tree DP, Standard DP and Advanced DP optimizations.
Bookmark this page and practice each problem.
Table of Contents:
 Mathematical DP
 Combination DP
 String DP
 Tree DP
 Standard DP
 Advanced DP optimizations
The list of problems in each category of Dynamic Programming is as follows:
Mathematical DP
 Longest Increasing Subsequence
 Longest Decreasing Subsequence
 Longest Common Subsequence
 Longest Common Increasing Subsequence
 Longest Common Decreasing Subsequence
 Longest Increasing Odd Even Subsequence
 Shortest Common SuperSequence
 Maximum Sum Subsequence
 Maximum Sum Subsequence of size K
 Maximum Sum Increasing Subsequence
 Maximum Sum Decreasing Subsequence
 Maximum Sum Increasing Subsequence of size K
 Maximum Sum Alternating Subsequence
 Longest Alternating Subsequence
 Count all subsequences in an array with product less than K
 Maximum product of an increasing subsequence
 Minimum number of elements which are not part of Increasing or decreasing subsequence in array
 Newman Conway Sequence
 Binomial Coefficient
 Permutation Coefficient
 nth Fibonacci number
 Longest Arithmetic Progression
 Number of arithmetic progression subsequences
 Longest Geometric Progression
 Longest Bitonic Sequence
 Maximum sum bitonic subsequence
 Find if a Subset with sum divisible by m exist
 Find Number of Subset with sum divisible by M
 Fibonacci Series in Reverse Order
 Largest rectangular sub matrix having sum divisible by k
 Maximum Sum Rectangle in a Matrix
 Largest subset with divisible pairs
 Break a number in 3 parts (n/2, n/3, n/4) recursively to get maximum sum
 Partition a set into two subsets such that sum of each subset is same
 Minimum number of increment or decrement (by 1) operations to make array in increasing order
 Minimum number of increment or decrement (by 1) operations to make array in decreasing order
Combinations DP
 Subset Sum Problem
 Same Sum Subset
 Number of ways to pair elements
 number of subsets of an array having a given XOR value
 number of subsets with given Bitwise OR value
 Number of non unique Partitions of an Integer
 Number of unique partitions of an integer
 Number of ways to reach a given number using increments of 1 and 2
 Number of ways to reach a number using increments of 1 and 2 (consecutive 2s are not allowed)
 Number of ways to reach a number using increments of 1 and 2 (consecutive 1s are not allowed)
 Number of ordered pairs such that (A[i] & A[j])=0
 number of sub matrices having sum divisible by K
 number of subsets with sum divisible by given number M
String DP
 Longest Common Substring
 Longest Common Subsequence
 Longest Palindromic Substring
 Longest Palindromic Subsequence
 Ways to increase LCS length of two strings by one
 Find if a string is interleaved of two other strings
 Number of substrings divisible by 8 but not 3
 Number of ways to insert a character to increase the LCS by one
 Number of ways to divide string in substrings such to make them in lexicographically increasing sequence
 Longest repeating and non overlapping substring in a string
 minimum number of deletions to make a string palindrome
 Palindrome Partitioning
 Minimum number of characters to be deleted to make string a palindrome
Tree DP

Minimum Cost Path in 2D matrix (+)

Maximum Cost Path in 2D matrix (+)

Maximum average value path in a 2D matrix (Restricted)

Minimum average value path in a 2D matrix (Restricted)

Count paths from Top Left to Bottom Right of a Matrix

Minimum Cost for Triangulation of a Convex Polygon

Largest Independent Set in Binary Tree

Number of paths with k edges

Shortest Path with k edges

Vertex Cover Problem

Binary Lifting with kth ancestor

Minimum number of Nodes to be removed such that no subtree has more than K nodes

Minimum number of nodes to be deleted so that at most k leaves are left

Minimum number of nodes to be deleted so that k leaves are left (*)
Standard DP
 Dice Throw Problem
 Assembly Line Scheduling
 Boolean Parenthesization Problem
 Matrix Chain Multiplication
 Egg Dropping Puzzle
 Maximum Length Chain of Pairs
 Box stacking Problem
 Coin Change Problem
 Minimum Coin Exchange Problem
 Rod cutting problem
 Maximum product cutting problem
 Unbounded Knapsack Problem
 Tile Stacking Problem
 Word Break Problem
 Word Wrap Problem
Advanced DP optimizations
 Knuth's optimization
 Breaking string with cost
 Divide and Conquer Optimization
 Group people to reduce unfamiliarity
With this article at OpenGenus, you have over 100 problems based on Dynamic Programming from beginner to advanced level. Bookmark this page and practice each problem.