Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
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.
How To Ace Dynamic Programming in Competitions
Author
0 upvotes
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.
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.
Tabulation vs Memoization EASY
This article discusses the difference between tabulation and memorization. Check out the algorithms and code implementations.
Overlapping substructure vs overlapping sub problems
This blog will cover the Optimal substructure and Overlapping subproblems.
Basics of DP with Trees MEDIUM
Dynamic Programming (DP) is a problem-solving approach that breaks down complex problems into smaller
Objective of The Knapsack Problem
This article will discuss various types of knapsack problems along with their properties, objectives, methodologies and variations.
Subsets
This article is based on the Subset problem asked in various coding competitions.
Coin Change: Minimum Number Of Coins MEDIUM
This article discusses different approaches to solve the coin change problem, which is to find the minimum number of coins needed to make a given amount
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.
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.
Longest Repeating Subsequence MEDIUM
The term "longest repeated subsequence" refers to a subsequence within a string that occurs more than once. Read on to learn more!
Author Riya
1 upvote
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.
Finding the Longest Common Subsequence (LCS) in given K permutations
The blog aims to find the Longest Common Subsequence in given K permutations.
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.
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.
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.
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.
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.
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.
Make all Array Elements Equal by Replacing Consecutive occurrences of a Number Repeatedly
This article will discuss the problem "Make all array elements equal by replacing consecutive occurrences of a number repeatedly," the solution approach to this problem, its C++ implementation, and its time and space complexity.
Author Riya
1 upvote
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 Algorithm 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.
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'll build a dynamic programming solution to the classic cherry pickup problem step by step, starting with brute force.
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.
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.
Mobile Numeric Keypad Problem
In this blog, we will learn about an interesting problem, the Mobile numeric keypad problem.
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 MEDIUM
Digit DP is a dynamic programming technique used to solve problems involving digit manipulation. It optimizes calculations and reduces redundancy, improving time and space complexity.
Longest Increasing Subsequence Size
This article will discuss the O(n logn) approach to find the longest increasing subsequence size.
Matchsticks to Square MEDIUM
In this article, we will discuss the problem of Matchsticks to Square.This problem is solved with method of recursion
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.
Filling Bookcase Shelves
In this blog, we'll be discussing the brute force and dynamic programming approach to the problem 'Filling Bookcase Shelves.'
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.‌
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.
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.
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.
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.
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’.
Finding the Minimum Cost to Reduce the Array by Merging the Adjacent Elements Repetitively MEDIUM
This article will discuss the problem of finding the minimum cost to reduce the array by merging the adjacent elements repetitively along with its solution approach and implementation in C++ language.
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.
Count of sequence of length K in the range [1, N] where every element is a multiple of its previous one
In this blog, we are going to discuss an interesting problem: Count of sequence of length K in the range [1, N] where every element is a multiple of its previous one. We are also going to discuss the space and time complexity of the approaches discussed.
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.
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.
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.