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.

Introduction

Dynamic Programming (DP) is an algorithmic technique used when solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems. It is not efficient in terms of memory: Since recursion involves function calls, each recursive call creates an entry for all the variables and constants in the function stack. These values are kept there until the function returns. Therefore, recursion is always limited by the stack space in the system.

How to solve a dynamic programming problem?

By Pradipta Choudhury

● Published At Dec 2021

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

Memoization vs Tabulation

By Reet Maggo

● Published At Oct 2021

This article will discuss and compare the working of tabulation and memoization in dynamic programming with the help of a code snippet and algorithm for the chosen example while also discussing the time and space complexity for the same.
... Keep reading ..

Overlapping substructure vs overlapping sub problems

By Nishant Rana

● Published At Feb 2022

This blog will cover the Optimal substructure and Overlapping subproblems.
... Keep reading ..

0-1 Knapsack and Variations

Knapsack simply means bag. A bag of given capacity. We have to pack n items into this bag, and every item has some weight and value. We have to make sure the total weight of items is less than or equal to the weight that a bag can hold. At the same time, we have to maximize the value of items packed in the bag. This is the basics of the Knapsack problem. Now 0-1 Knapsack says you can either take the item as a whole or not, but you cannot break the item and take some part of it.

Subsets

By Aditya Narayan Joardar

● Published At Nov 2021

This article is based on the Subset problem asked in various coding competitions.... Keep reading ..

0-1 Knapsack

By Harsh Goyal

● Published At Dec 2021

This article will discuss the 0-1 Knapsack problem and various ways to solve this problem.... Keep reading ..

Count Number of subsets with given Sum

By Sneha Mallik

● Published At Oct 2021

This blog covers the concept of counting the number of subsets with a given sum. We will learn about its implementation, algorithm, time complexity and space complexity.
... Keep reading ..

Subset Sum Problem

By Nishant Rana

● Published At Oct 2021

This blog will cover the question Subset Sum Problem and discuss its Time and Space complexity.... Keep reading ..

Coin Change: Minimum Number Of Coins

By Deeksha

● Published At Oct 2021

This blog will discuss the three approaches to the most asked questions: coin change the minimum number of coins along with the discussion on their time and space complexities.... Keep reading ..

Unbounded Knapsack

By Reet Maggo

● Published At Dec 2021

This article will explain the various knapsack problems and especially illustrate the Unbounded Knapsack while explaining its working with the help of a code snippet and algorithm. The blog will further discuss time and space complexity for Unbounded... Keep reading ..

Target Sum

By Deeksha Rajput

● Published At Dec 2021

In this blog, we will be discussing three approaches for a problem target sum along with their space and time complexities. Target sum is the frequently asked question in all tech interviews.... Keep reading ..

LCS and Variations

The longest common subsequence of two strings is the length of the longest subsequence, which is common to both the given strings. It is a classical DP problem and thus has different variations, including Longest common substring, Shortest common supersequence, the Longest palindromic subsequence, etc. All these problems have similar code structures and fall under the category of LCS.

Longest Common Subsequence

By Raksha Jain

● Published At Dec 2021

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

Longest common substring

By Riya

● Published At Feb 2022

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

Longest Palindromic Subsequence

By Nishant Rana

● Published At Oct 2021

In this blog, we will cover the question of finding the Longest Palindromic Subsequence and discussion over its Time and Space complexity.... Keep reading ..

Minimum insertion to convert the string to a palindrome

By Nishant Rana

● Published At Oct 2021

This blog will see how to calculate the minimum number of insertions to convert the given string to a palindrome string along with the discussion in time and space complexities.... Keep reading ..

Longest Repeating Subsequence

By Riya

● Published At Jan 2022

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

LCS of 3 strings

By Saksham Gupta

● Published At Dec 2021

In this blog, we will discuss the extension of LCS of two strings and will see how we can calculate LCS of 3 strings.... Keep reading ..

Shortest Common Supersequence

By Deeksha

● Published At Dec 2021

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

Distinct subsequences

By Pranav Gautam

● Published At Nov 2021

Learn to find the occurrence of distinct subsequences in a sequence.... Keep reading ..

Expression Matching

Expression Matching is a problem based on the practical application of dynamic programming. Regular expressions, often known as regexes, are character sequences that are used to find a pattern in a string or set of strings. We have two strings, say string s and string p. String p may contain ‘.’ And ‘’. Now our aim is to implement regular expression matching such that ‘.’ May match any single character and ‘’ may match zero or more of the preceding elements.

Regular Expression Matching

By vaishnavi pandey

● Published At Nov 2021

In this article, we’ll see various approaches to solve the regular expression matching problems.... Keep reading ..

Wildcard Matching

By Shreya Deep

● Published At Oct 2021

We’ll learn how to solve a problem named wildcard matching where we have to determine whether a pattern can be matched to a given text or not. ... Keep reading ..

Stock Variations

We all know about arrays as a data structure, but then where are they practically used?
An important application of arrays in competitive programming is in stock variations.
This topic focuses on the different problems on the best time to buy and sell a stock.

Best time to buy and sell stock

By Manvi Chaddha

● Published At Oct 2021

This blog will discuss an important interview problem, the best time to buy and sell stock. Various approaches along with Java code are discussed.... Keep reading ..

Best time to buy and sell stock II

By Manvi Chaddha

● Published At Oct 2021

The best time to buy and sell stock is an important interview problem. This blog discusses the solution for it.... Keep reading ..

Best Time to Buy and Sell Stock III

By Ishita Chawla

● Published At Dec 2021

In this blog, we will be discussing the famous problem, Best time to Buy and Sell Stock III, and solve it using two different techniques, subsequently analyzing its time and space complexity.
... Keep reading ..

Best Time to Buy and Sell Stock with at most K Transactions

By Yukti Kumari

● Published At Oct 2021

The article explains the problem’s solution - Best Time to buy and sell stock with at most K transactions. Both Recursive and DP approaches have been discussed.... Keep reading ..

Best time to buy and sell stock with cooldown

By Shreya Deep

● Published At Nov 2021

In this article, we’ll learn how to gain the maximum profit by finding the best time to buy and sell stock as many times as we want. ... Keep reading ..

Problems

All of us have heard of dynamic programming and know that it is used in various applications asked in interviews, but what are those applications?
Some common problems using dynamic programming are:
1. Edit Distance
2. Palindromic partitioning
3. Tiling Problem
4. Building Bridges
These are just a few out of the many discussed in the section below.

Edit Distance

By Aman kumar Chourasiya

● Published At Jan 2022

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

Wine Selling

By Aanchal Tiwari

● Published At Oct 2021

Today, we will have a walkthrough of a classical interview problem named Wine Selling Problem. This question has come up in several coding interviews.... Keep reading ..

Maximum Product Subarray

By Yukti Kumari

● Published At Oct 2021

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

Maximum Area of the Square Submatrix

By Aditya Narayan Joardar

● Published At Oct 2021

In this article, we discuss the problem of the maximum area of the square submatrix on a given binary matrix. ... Keep reading ..

Maximal Square

By Alisha Chhabra

● Published At Nov 2021

This article covers the crucial question of Dynamic programming, i.e., Maximal Square, in detail.
... Keep reading ..

Longest Valid Parenthesis

By Shreya Deep

● Published At Oct 2021

In this article, we’ll learn how to find the length of the longest valid parentheses... Keep reading ..

Minimum Sum Path in a Matrix

By Aditya Narayan Joardar

● Published At Oct 2021

This article is concerned with the minimum sum path in a matrix. We need to find the minimum sum path using the input matrix.
... Keep reading ..

Maximum Profit In Job Scheduling

By Shreya Deep

● Published At Oct 2021

In this article, we’ll learn to find the maximum profit earned in job scheduling along with the implementation in C++.
... Keep reading ..

Number of unique good subsequences

By Yukti Kumari

● Published At May 2022

The article explains the solution of the problem to find the number of unique good subsequences in a given binary string and its time and space complexities.... Keep reading ..

Kingdom War

By Aditya Narayan Joardar

● Published At Oct 2021

This article discusses the Kingdom War problem seen in many competitive coding platforms.
... Keep reading ..

Longest Increasing Subsequence | Part 1

By Aditya Narayan Joardar

● Published At Oct 2021

This is a two-part article based on: Longest Increasing Subsequence. In this part, we shall discuss the iterative and semi-optimized DP solutions.
... Keep reading ..

Longest Increasing Subsequence | Part 2

By Aditya Narayan Joardar

● Published At Oct 2021

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

Largest Sum of Averages

By Husen Kagdi

● Published At Feb 2022

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

Interleaving Strings

By Ishita Chawla

● Published At Oct 2021

In this blog, we will discuss the problem, Interleaving strings, a primitive problem of Dynamic Programming, and its time and space complexity.
... Keep reading ..

Minimum Score Triangulation of Polygon

By Yukti Kumari

● Published At Oct 2021

This article explains the solution of minimum score triangulation of polygon using dynamic programming.
... Keep reading ..

Super Ugly Numbers

By Ishita Chawla

● Published At Dec 2021

This blog will discuss a variation of the famous problem, Ugly Numbers, and shed some light on its time and space constraints.
... Keep reading ..

Longest Palindromic Substring

By Nishant Rana

● Published At Oct 2021

In this blog, we will cover the question Longest Palindromic Substring and discussion over its Time and Space complexity.
... Keep reading ..

Distinct subsequences

By Pranav Gautam

● Published At Nov 2021

Learn to find the occurrence of distinct subsequences in a sequence.... Keep reading ..

Matrix Chain Multiplication

By Husen Kagdi

● Published At Nov 2021

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

Matrix Chain Multiplication

By Husen Kagdi

● Published At Feb 2022

In this blog, we will discuss an important dynamic programming question, matrix chain multiplication. Dynamic programming is the key to solve this problem.
... Keep reading ..

Evaluate expression to true

By Saksham Gupta

● Published At Dec 2021

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

Cherry Pickup

By Firdausia Fatima

● Published At Oct 2021

In this blog, we'll build a dynamic programming solution to the classic cherry pickup problem step by step, starting with brute force.
... Keep reading ..

Dungeon Game

By Saksham Gupta

● Published At Dec 2021

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

Box Stacking

By Harsh Goyal

● Published At Dec 2021

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

Egg dropping problem

By Pranav Gautam

● Published At Nov 2021

Learn to find the minimum number of egg drops required in the worst case for the given number of eggs and floors.... Keep reading ..

Mobile Numeric Keypad Problem

By Husen Kagdi

● Published At Jan 2022

In this blog, we will learn about an interesting problem, the Mobile numeric keypad problem.... Keep reading ..

Tiling Problem

By Ishita Chawla

● Published At Oct 2021

This blog will discuss the Tiling Problem, a fundamental problem of Dynamic Programming, and analyze its time and space complexity.
... Keep reading ..

Building Bridges

By Ishita Chawla

● Published At Nov 2021

This blog will discuss Building Bridges, a variation of the Longest Increasing Subsequence problem, and discuss its time and space complexity. ... Keep reading ..

Palindromic Partitioning II

By Pranav Gautam

● Published At Nov 2021

Learn to find the minimum number of string partitions required to make all the substrings of a string a palindrome.... Keep reading ..

Longest Increasing Subsequence Size

By Soumya Agrawal

● Published At Mar 2022

This article will discuss the O(n logn) approach to find the longest increasing subsequence size.... Keep reading ..

Check for Binary Search Tree

By GAZAL ARORA

● Published At Dec 2021

In this article, you will learn that if you are given an array and an extra condition to satisfy, how to find if a Binary Search Tree can be created from that given array or not.... Keep reading ..

Coin Change Combination Problem

By Raksha Jain

● Published At Dec 2021

The blog discusses in detail the Coin Change Combination Problem. We’ll discuss many approaches to solve the problem and time and space complexity for each method.... Keep reading ..

Path Requiring a Minimum Number of Jumps to Reach the End of the Array

By Yogesh Kumar

● Published At Nov 2021

In this blog, we will solve the problem of finding the Paths requiring a minimum number of jumps to reach the end of array.... Keep reading ..

Longest Subarray whose Elements can be made Equal by Maximum K Increments

By Anant Dhakad

● Published At Jan 2022

In this blog, we will discuss a coding problem based on sliding window technique, prefix sum and use of deque data structure to find the maximum element in a subarray. We will learn to combine these techniques to find the optimal solution.... Keep reading ..

Filling Bookcase Shelves

By Firdausia Fatima

● Published At Jan 2022

In this blog, we'll be discussing the brute force and dynamic programming approach to the problem 'Filling Bookcase Shelves.'... Keep reading ..

Check if an Original String Exists Given Two Encoded Strings

By Firdausia Fatima

● Published At Jan 2022

In this blog, we’ll solve an advanced DP problem, Check if an Original
String Exists given two Encoded Strings. ... Keep reading ..

Minimum Number of Taps to Open to Water a Garden

By Yogesh Kumar

● Published At Nov 2021

In this blog, we will solve one of the problems Minimum Number of Taps to Open to Water a Garden of “Hard” categories, from brute force to an optimized approach.... Keep reading ..

Rod Cutting Problem

By Raksha Jain

● Published At Feb 2022

The blog discusses in detail the Rod Cutting Problem. We’ll discuss many approaches to solve the problem along with time and space complexity for each method.... Keep reading ..

Palindrome Partitioning

By Husen Kagdi

● Published At Feb 2022

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

Scramble String

By Ishita Chawla

● Published At Oct 2021

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

Largest Divisible Subset

By aniket verma

● Published At Dec 2021

This article will brief you on finding the Largest Divisible Subset.... Keep reading ..

Largest Sum of Averages

By Husen Kagdi

● Published At Dec 2021

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

Burst Baloon

By Nishant Rana

● Published At Feb 2022

This blog will cover the question Burst Balloon and discuss their Time and Space complexity.
... Keep reading ..

Maximum size of rectangle in a binary matrix

By Pranav Gautam

● Published At Nov 2021

Learn to find the area of the largest rectangle possible in a binary matrix with all 1s.... Keep reading ..

Russian Doll Envelopes

By Husen Kagdi

● Published At Nov 2021

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

Numbers with Repeated Digits

By Aman kumar Chourasiya

● Published At Jan 2022

In this blog, we discuss an exciting problem, namely, Numbers with repeated digits. We will discuss a construction to solve this problem efficiently.... Keep reading ..

## Top Problems related to Dynamic Programming

Longest Common Subsequence

Palindromic Substrings

Colorful Knapsack

Edit Distance

Minimum Cost To Buy Oranges

Longest Increasing Subsequence

Tiling Problem

Ways To Make Coin Change

House Robber

Minimum Cost Path

Maximum Subarray Sum

Common Digit Longest Subsequence

Simplify the Directory

Best Time to Buy and Sell

Nth Number

Wildcard Pattern Matching

Longest Palindromic Substring

Maximum Coins

Word Break-1

Count Ways

Break Number