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 sum, tree diameter, and maximum path sum are some examples of DP on trees problems. All of these problems have one thing in common: we get the answers for the left and right subtrees, then apply some math to find answers for the root.
Basics of DP with Trees
By Saksham Gupta
● Published At Dec 2021
In this blog, we will discuss how we can apply dynamic programming on trees and will understand its implementation by taking various examples. ... Keep reading ..
Maximum sum path from the leaf to leaf(Extend it to any node to any node)
By Saksham Gupta
● Published At Dec 2021
In this blog, we will discuss how we can calculate the maximum sum path from leaf to leaf in a binary tree. Further, we’ll extend it to the maximum sum path from any node to any node in a binary tree. ... Keep reading ..
Sum of the Length of Paths from Every Node to All Other Nodes
By Soumya Agrawal
● Published At Mar 2022
This article will cover the approach and implementation of the problem- Sum of the Length of Paths from every Node to all other Nodes using the Tree Rerooting technique.... Keep reading ..
Unique Binary Search Trees
By Rubleen Kaur
● Published At Jan 2022
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 that the naïve (n!) brute force solution may be lowered to (2^n ) by iterating over subsets rather than permutations. Bit operations provide an efficient and straightforward technique to create dynamic programming algorithms whose states comprise subsets of elements.
By Nishant Rana
● Published At Mar 2022
This blog will cover the famous NP-Hard problem Travelling Salesman Problem. We will be solving it using DP with BitMasking. ... Keep reading ..
Number of Ways to Wear Different Hats to Each Other
By Raksha Jain
● Published At Feb 2022
The blog discusses in detail the Number of Ways to Wear Different Hats to Each Other. We’ll discuss different approaches to solve the problem and time and space complexity for each method.... Keep reading ..
Count the number of ways you can give each person a different cap
By Gaurish Anand
● Published At Feb 2022
This article explains how to count the number of ways to give each person a different cap when we have 50 different types of caps.... Keep reading ..
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 problems require us to count the number of numbers in a range that satisfies a particular property. If this property is dependent only on the digits of a number rather than its actual value, we can use digit DP. Some examples of such properties are divisibility by 3/9, the sum of digits, etc."
Introduction to Digit DP
By Abhishek Ranjan
● Published At Dec 2021
In this article, we will discuss the basics of Digit DP and try to solve an example problem.... Keep reading ..
Introduction to digit DP
By Pranav Gautam
● Published At Nov 2021
An introductory blog to get started with Digit DP. Learn to solve digit DP problems with the help of an example.... Keep reading ..
Count numbers from a given range whose product of digits is K
By Firdausia Fatima
● Published At Dec 2021
In this blog, we'll talk about two approaches to count numbers from a given range whose product is K.... Keep reading ..
Count of numbers from the range [L, R] whose sum of digits is Y
By Husen Kagdi
● Published At Dec 2021
In this blog, we will discuss a range query problem named count of numbers from the range [L, R] whose sum of digits is Y. ... Keep reading ..
Find Count of numbers from a given range whose product of digits is X
By Apoorv
● Published At Feb 2022
This article will discuss the solution for the problem statement 'Find Count of numbers from a given range whose product of digits is X’. The article will discuss both naive and optimized approaches along with the time and space complexity of both so... Keep reading ..
Count of N digit numbers which contains all single-digit primes
By Ayush Prakash
● Published At Feb 2022
In this blog, we will discuss an interesting problem: Count of N digit numbers which contains all single-digit primes. We will also discuss the time and space complexity of the approaches discussed. ... Keep reading ..
How to find all N digit numbers with at least one repeated digit
By Ujjawal Gupta
● Published At Jan 2022
In this blog, we will learn to solve a problem based on Dynamic Programming. We will discuss three approaches based on number theory, dynamic programming, and Combinatorics.... Keep reading ..
Total count of sorted numbers up to N digits in the range [L, R]
By Nishant Rana
● Published At Feb 2022
This blog will cover the question to find the count of the total sorted numbers of up to N digits in the range [L, R]. ... Keep reading ..
Count of N-digit Numbers whose bitwise AND Of Adjacent Digits Equals 0
By Rhythm Jain
● Published At Dec 2021