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

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 ..

## Top Problems related to Dynamic Programming

Binary Search

Compress the String

Generate all parenthesis

Count Inversions

Longest Common Subsequence

Anagram Pairs

Longest Common Prefix

Maximum Subarray Sum

Move Zeroes To End

Insert Interval

Product Of Array Except Self

Convert Given Number To Words

Best Time to Buy and Sell Stock II

Check If Given Numbers Are Coprime

Convert Min-Heap to Max-Heap

Palindromic Substrings

Colorful Knapsack

Overlapping Intervals

Longest Substring Without Repeating Characters

Last Stone Weight

Edit Distance