 New update is available. Click here to update.
Last updated: Aug 2, 2022

# 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.
Getting Started with Dynamic Programming - Part 1
we have discussed dynamic programming, what kind of problems can be solved by dynamic programming, the difference between DP and Recursion, and finally, variations of problems in Dynamic Programming. Author Ankit kumar 0 upvotes
How to solve a dynamic programming problem?
This article covers dynamic programming; how we can approach it, a discussion around its time and space complexity, and finally has gone through a hands-on example.
Overlapping substructure vs overlapping sub problems
This blog will cover the Optimal substructure and Overlapping subproblems.
Basics of DP with Trees MEDIUM
In this blog, we will discuss how we can apply dynamic programming to trees and will understand its implementation by taking various examples. Author Vibhor_376 0 upvotes
Objective of The Knapsack Problem
This article will discuss various types of knapsack problems along with their properties, objectives, methodologies and variations. Author Alankrit Srivastava 3 upvotes
Subsets
Coin Change: Minimum Number Of Coins MEDIUM
This blog will discuss the three approaches to the most asked questions: coin change, the minimum number of coins and the time and space complexities. Author Rhythm Jain 0 upvotes
Longest Common Subsequence MEDIUM
The blog discusses in detail the Longest Common Subsequence. We’ll discuss many approaches to solve the problem and time and space complexity for each method. Author Zenith 1 upvote
Longest common substring MEDIUM
This article will discuss the Longest Common Substring problem and various ways to solve it, from the brute force solution to the dynamic programming solution and their space and time complexities. Author Riya 3 upvotes
Longest Palindromic Subsequence
In this blog, we will cover the question of finding the Longest Palindromic Subsequence and discussion over its Time and Space complexity.
Longest Repeating Subsequence MEDIUM
This article will discuss the Longest Repeating Subsequence problem and various ways to solve it, starting from the brute force solution to dynamic programming solution and their space and time complexities. Author Riya 0 upvotes
LCS of 3 strings
In this blog, we will discuss the extension of LCS of two strings and will see how we can calculate LCS of 3 strings.
Shortest Common Supersequence
In this blog, we will be discussing the problem shortest Common Supersequence. We will be starting from brute force and will be optimizing it using dynamic programming. Author Deeksha 0 upvotes
Finding the Longest Common Subsequence (LCS) in given K permutations
The blog aims to find the Longest Common Subsequence in given K permutations.  0 upvotes
Edit Distance
In this blog, we will discuss a problem based on dynamic programming. Dynamic programming is a well-known topic asked in programming contests and coding interviews.
Wine Selling
Today, we will have a walkthrough of a classical interview problem named Wine Selling Problem. This question has come up in several coding interviews. Author Aanchal Tiwari 2 upvotes
Maximum Product Subarray MEDIUM
This article explains the solution to a coding problem to find the maximum product subarray from a given array in linear time and using constant space. Author Yukti Kumari 0 upvotes
Maximum Area of the Square Submatrix
In this article, we discuss the problem of the maximum area of the square submatrix on a given binary matrix.
Greatest Sum Divisible by Three
This blog finds the maximum sum from the array such that the sum is divisible by three
Maximal Square
This article covers the crucial question of Dynamic programming, i.e., Maximal Square, in detail. Author Alisha 2 upvotes
Longest Valid Parentheses MEDIUM
A sequence of parentheses is called balanced if, for every opening bracket, there is a unique closing bracket.
Minimum Sum Path in a Matrix MEDIUM
In this article, we discuss one of the famous matrix problems - Minimum Sum Path in a Matrix and some of the approaches and implementations to solve it in C++, Java, and Python.
Maximum Profit In Job Scheduling
In this article, we’ll learn to find the maximum profit earned in job scheduling along with the implementation in C++.
Kingdom War
This article discusses the Kingdom War problem seen in many competitive coding platforms.
kth smallest absolute difference of two elements in an array
In this article, we will discuss how to find the k maximum sums of non-overlapping contiguous sub-arrays, in detail. Author Rupal Saluja 0 upvotes
Longest Increasing Subsequence | Part 1 EASY
This is a two-part article based on: Longest Increasing Subsequence. In this part, we shall discuss the iterative and semi-optimized DP solutions.
Longest Increasing Subsequence | Part 2
This is a two-part article based on: Longest Increasing Subsequence. This is part two of the article, which discusses the highly optimized DP solution.
Largest Sum of Averages
In this blog, we will discuss a Leetcode medium problem, namely, the largest sum of averages. It has been asked by Facebook, Microsoft, and Amazon. Author Husen Kagdi 0 upvotes
Interleaving Strings
In this blog, we will discuss the problem, Interleaving strings, a primitive problem of Dynamic Programming, and its time and space complexity.
Super Ugly Numbers
This blog will discuss a variation of the famous problem, Ugly Numbers, and shed some light on its time and space constraints.
Smallest Subarray With All Occurrences of the Most Frequent Element MEDIUM
This article gives you an in-depth solution to the question solution of the Smallest Subarray With All Occurrences of the Most Frequent Element. Author Shiva 0 upvotes
Distinct Subsequences HARD
The following article explores the popular Distinct Subsequences problem in which we determine the number of distinct subsequences present in the string along with their frequency.
Matrix Chain Multiplication EASY
In this blog, we will discuss an important dynamic programming question, matrix chain multiplication. It is a foundational problem to solve different problems of the same types. Author Husen Kagdi 0 upvotes
Evaluate expression to true
In this blog, we will discuss one of the classical problems asked in dynamic programming and an all-time favorite problem for coding interviews, i.e., evaluate expression to true.
Cherry Pickup HARD
In this blog, we&#39;ll build a dynamic programming solution to the classic cherry pickup problem step by step, starting with brute force. Author Firdausia Fatima 1 upvote
Dungeon Game
In this blog, we will discuss one of the trickier questions asked in dynamic programming, i.e., Dungeon Game. We will look at all possible approaches to the given problem.
Box Stacking
This article will discuss the box stacking problem and various ways to solve this problem, starting from the brute force approach to the efficient approach. Author Harsh Goyal 0 upvotes
Egg dropping problem EASY
Learn to find the minimum number of egg drops required in the worst case for the given number of eggs and floors.
In this blog, we will learn about an interesting problem, the Mobile numeric keypad problem. Author Husen Kagdi 0 upvotes
Find the minimum cost to reach the destination using a train MEDIUM
In this blog, we have discussed a problem statement based on dynamic programming called Find the minimum cost to reach the destination using a train Author Shiva 0 upvotes
Palindromic Partitioning II
Learn to find the minimum number of string partitions required to make all the substrings of a string a palindrome.
Introduction to Digit DP
In this article, we will discuss the basics of Digit DP and try to solve an example problem.
Introduction to digit DP
An introductory blog to get started with Digit DP. Learn to solve digit DP problems with the help of an example.
Longest Increasing Subsequence Size
This article will discuss the O(n logn) approach to find the longest increasing subsequence size. Author Soumya Agrawal 0 upvotes
Matchsticks to Square MEDIUM
In this article, we will discuss the problem of Matchsticks to Square.This problem is solved with method of recursion Author Vibhor_376 0 upvotes
Path Requiring a Minimum Number of Jumps to Reach the End of the Array
In this blog, we will solve the problem of finding the Paths requiring a minimum number of jumps to reach the end of array. Author Yogi21 0 upvotes
Filling Bookcase Shelves
In this blog, we'll be discussing the brute force and dynamic programming approach to the problem 'Filling Bookcase Shelves.' Author Firdausia Fatima 0 upvotes
Check if an Original String Exists Given Two Encoded Strings
In‌ ‌this‌ ‌blog,‌ ‌we’ll‌ ‌solve‌ ‌an‌ ‌advanced‌ ‌DP‌ ‌problem,‌ ‌Check‌ ‌if‌ ‌an‌ ‌Original‌ ‌ String‌ ‌Exists‌ ‌given‌ ‌two‌ ‌Encoded‌ ‌Strings.‌ Author Firdausia Fatima 0 upvotes
Palindrome Partitioning MEDIUM
This blog discusses the palindrome partitioning problem. It is a variation of the Matrix Chain Multiplication problem. It can be easily solved using dynamic programming. Author Teesha Goyal 0 upvotes
Palindrome Partitioning
This blog discusses the palindrome partitioning problem. It is a variation of the Matrix Chain Multiplication problem. It can be easily solved using Dynamic programming. Author Husen Kagdi 0 upvotes
Scramble String MEDIUM
In this blog, we will discuss the problem of Scramble String and solve it using recursion and dynamic programming, analyzing the time and space complexity in both cases.
Largest Sum of Averages
In this blog, we will discuss a Leetcode medium problem, namely, the largest sum of averages. It has been asked in interviews with top product-based companies such as Facebook, Microsoft, and Amazon. Author Husen Kagdi 0 upvotes
Burst Baloon MEDIUM
This blog discusses the popular problem Burst Baloon along with its solution ranging from the most intuitive to most optimal one.
Maximum Product of Two Non-intersecting Paths in a Tree HARD
This article incorporates how you find the maximum product of two non-intersecting paths in a tree. Author Amit Singh 0 upvotes
Minimum Count of Prefixes and Suffixes of a String Required to Form Given String
In this blog, we will see how we can solve the famous problem ‘minimum count of prefixes and suffixes of a string required to form given string’.
Maximum size of rectangle in a binary matrix
Learn to find the area of the largest rectangle possible in a binary matrix with all 1s.
Russian Doll Envelopes
In this blog, we will discuss an exciting problem named Russian Doll Envelopes. It is a variation of the Longest Increasing Subsequence (LIS) problem. It is a 2D version of LIS. Author Husen Kagdi 0 upvotes
Numbers with Repeated Digits
In this blog, we discuss an exciting problem, namely, Numbers with repeated digits. We will discuss a construction to solve this problem efficiently.
Maximum Subarray Sum: Kadane's Algorithm EASY
This article discusses the introduction of subarray and then we will discuss the kadane algorithm that is used for finding the maximum sum contiguous subarray. Go on top