Dynamic Programming (DP) Problems
We have classified standard dynamic programming (DP) problems into three categories: Easy, Medium, and Hard.
1. Easy Problems on Dynamic Programming (DP)
- Fibonacci numbers
- nth Catalan Number
- Bell Numbers (Number of ways to Partition a Set)
- Binomial Coefficient
- Coin change problem
- Subset Sum Problem
- Compute nCr % p
- Cutting a Rod
- Painting Fence Algorithm
- Longest Common Subsequence
- Longest Increasing Subsequence
- Longest subsequence such that difference between adjacents is one
- Maximum size square sub-matrix with all 1s
- Min Cost Path
- Minimum number of jumps to reach end
- Longest Common Substring (Space optimized DP solution)
- Count ways to reach the nth stair using step 1, 2 or 3
- Count all possible paths from top left to bottom right of a mXn matrix
- Unique paths in a Grid with Obstacles
2. Medium Problems on Dynamic Programming (DP)
- Floyd Warshall Algorithm
- Bellman–Ford Algorithm
- 0-1 Knapsack Problem
- Printing Items in 0/1 Knapsack
- Unbounded Knapsack (Repetition of items allowed)
- Egg Dropping Puzzle
- Word Break Problem
- Vertex Cover Problem
- Tile Stacking Problem
- Box-Stacking Problem
- Partition Problem
- Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming)
- Longest Palindromic Subsequence
- Longest Common Increasing Subsequence (LCS + LIS)
- Find all distinct subset (or subsequence) sums of an array
- Weighted job scheduling
- Count Derangements (Permutation such that no element appears in its original position)
- Minimum insertions to form a palindrome
- Wildcard Pattern Matching
- Ways to arrange Balls such that adjacent balls are of different types
3. Hard Problems on Dynamic Programming (DP)
- Palindrome Partitioning
- Word Wrap Problem
- The painter’s partition problem
- Program for Bridge and Torch problem
- Matrix Chain Multiplication
- Printing brackets in Matrix Chain Multiplication Problem
- Maximum sum rectangle in a 2D matrix
- Maximum profit by buying and selling a share at most k times
- Minimum cost to sort strings using reversal operations of different costs
- Count of AP (Arithmetic Progression) Subsequences in an array
- Introduction to Dynamic Programming on Trees
- Maximum height of Tree when any Node can be considered as Root
- Longest repeating and non-overlapping substring
Quick Links:
- Learn Data Structure and Algorithms | DSA Tutorial
- Top 20 Dynamic Programming Interview Questions
- ‘Practice Problems’ on Dynamic Programming
- ‘Quiz’ on Dynamic Programming
Dynamic Programming or DP
Dynamic Programming is a method used in mathematics and computer science to solve complex problems by breaking them down into simpler subproblems. By solving each subproblem only once and storing the results, it avoids redundant computations, leading to more efficient solutions for a wide range of problems. This article provides a detailed exploration of dynamic programming concepts, illustrated with examples.
Table of Content
- What is Dynamic Programming ?
- How Does Dynamic Programming Work?
- Examples of Dynamic Programming
- When to Use Dynamic Programming?
- Approaches of Dynamic Programming
- Dynamic Programming Algorithm
- Advantages of Dynamic Programming
- Applications of Dynamic Programming
- Learn Basic of Dynamic Programming
- Advanced Concepts in Dynamic Programming
- Dynamic Programming Problems