Dynamic Programming
Dynamic Programming is a technique of doing an optimization over recursion. We store the answer for the overlapping subproblems and use that result if we need the answer for the same problem in the future. Hence, we save the time of re-computing the answer for the same problem. It is a great technique that helps us to reduce the exponential time complexity to polynomial time complexity.
Basics
Dynamic Programming is a technique to solve a complex problem by breaking it in terms of smaller sub-problems followed by solving each subproblem only once. The main idea is to avoid repetitive computations. All the DP problems can be broadly classified into two categories: Optimization problems and combinatorial problems.
DP with Arrays
Arrays are one of the most basic and widely used data structures. Some of the interesting problems on arrays are solved using dynamic programming. Thi
DP with Strings
Some of the most exciting questions on strings reach exponential run times if solved by a usual brute force method. This is where DP comes in to help
DP with Maths
"Dynamic programming is a useful mathematical tool for making a series of decisions that are all related. In contrast to linear programming, ""the"" d
Breaking and Partitioning
This category contains an illustrative Dynamic programming problem based on breaking and partitioning. The main logic behind this problem is to partit
Counting Based
This category contains an illustrative Dynamic programming problem based on counting. We apply a bottom-up approach to solve the question. First, we c
scroll-indicator
scroll-indicator
Advanced
One of the most frightening topics in DSA is dynamic programming. To tackle a dynamic problem, first, create the recursive approach, then look for repeating problems, and finally memoize. This category is about solving advanced DP problems by identifying patterns, so you can learn not only how to solve that specific problem, but also how to solve advanced DP problems in general.
DP with Trees
When you need to use the solution to the left and right subtree to find the answer to the root, dynamic programming with trees is often relevant. Path
DP with bitmasking
Bitmask DP is often used for cases where the best solution may be naively deduced from some permutation of elements. The key point of bitmask DP is th
Digit DP
"Digit DP is a Dynamic Programming technique in which we focus on the digits of a number rather than its actual value. The most common digit DP proble
Mixed Problems
Dynamic Programming or DP is a fundamental algorithmic paradigm that breaks the problem at hand into smaller subproblems and stores the solutions of subproblems to avoid recomputation. The two main properties to identify that DP can solve a problem is, 1. Overlapping subproblem 2. Optimal substructure Here, we will be looking at some mixed problems on Dynamic Programming to understand this topic better.
Longest Bitonic Subsequence
By Sandeep kamila
● Published At Jan 2022
This article discusses the approach to finding the longest bitonic subsequence with complete explanation and its implementation in C++.... Keep reading ..
Maximise Difference Between Sum Of Even And Odd-Indexed Elements Of A Subsequence
By Rhythm Jain
● Published At Feb 2022
This article discusses the Problem, Maximise Difference Between Sum Of Even And Odd-Indexed Elements Of A Subsequence.... Keep reading ..
Maximum sum subsequence of any size that is decreasing-increasing alternatively
By Urwashi Priya
● Published At Jan 2022
This article will brief you on the problem of finding the maximum sum subsequence of any size that is decreasing-increasing alternatively. ... Keep reading ..
Count of valid arrays of size P with elements in the range [1, N] having duplicates at least M distance apart
By Aman kumar Chourasiya
● Published At Jan 2022
In this blog, we will take up a coding problem based on dynamic programming. We will see how to efficiently implement a recursive solution using memoization.... Keep reading ..
Check if a path exists from start to end cell in given Matrix with obstacles in at most K moves
By Abhishek Ranjan
● Published At Jan 2022
In this article, we will try to solve a graph theory problem that can be asked in the interviews... Keep reading ..
Longest subsequence such that the difference between adjacent elements is K
By Vibhor Bhatnagar
● Published At Jan 2022
In this article, we will discuss the problem find the longest subsequence such that the difference between adjacent elements is K.... Keep reading ..
Finding the Longest Common Subsequence (LCS) in given K permutations
By HET FADIA
● Published At Jan 2022
The blog aims to find the Longest Common Subsequence in given K permutations.... Keep reading ..
Greatest Sum Divisible by Three
By Ayush Tiwari
● Published At Jan 2022
This blog finds the maximum sum from the array such that the sum is divisible by three... Keep reading ..
puzzle icon

Top Problems related to Dynamic Programming