List of 100+ Dynamic Programming Problems

Internship at OpenGenus

Get FREE domain for 1st year and build your brand new site

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

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

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

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.