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:

1. Mathematical DP
2. Combination DP
3. String DP
4. Tree DP
5. Standard DP
6. 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
• n-th 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 sub-strings 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 k-th 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.