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?
● 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
● Published At Nov 2021
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
● 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
● 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
● 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
● Published At Oct 2021
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
● Published At Oct 2021
This article discusses the Kingdom War problem seen in many competitive coding platforms. ... Keep reading ..
Longest Increasing Subsequence | Part 1
● 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
● 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&#39;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 ..
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
● 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
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 ..