List of Dynamic Programming (DP) problems

Count all subsequences in an array with product less than K

Finding subsequences in an array with product less than a given number is another area of application of dynamic programming.

Algorithms

Introduction to Dynamic Programming

In this article, we will understand crux of Dynamic Programming, different methodologies for solving DP problems, identifying a DP problem and trying to solve a specific problem

Algorithms

Print Fibonacci Series in Reverse Order

In this article, we will explore how to print fibonacci series in reverse order. A key point to note here is that as Fibonacci number depends on previous fibonacci numbers

Algorithms

Find if a Subset with sum divisible by m exist

In this article, we find if a Subset with sum divisible by m exist. A naive approach takes O(2^N) time while dynamic programming takes O(N*M) time

Problems on Binary Tree

Largest Independent Set in Binary Tree

In this article, we solve the Largest Independent Set in Binary Tree problem using Dynamic Programming and use an augmented binary tree to achieve this.

Algorithms

Minimum Cost for Triangulation of a Convex Polygon

We find the Minimum Cost for Triangulation of a Convex Polygon using a dynamic programming approach in O(N^2) space and O(N^3) time complexity.

Algorithms

Find n-th Fibonacci number using Dynamic Programming

In this article, we have explored a dynamic programming approach to find the n th fibonacci number followed by a space optimized technique.

Algorithms

Solving Unbounded Knapsack Problem using Dynamic Programming

Restriction of limited items is removed in Unbounded Knapsack Problem. An item can be used infinite times and can be solved efficiently using Dynamic Programming.

Algorithms

Subset Sum Problem using Dynamic Programming 【O(N*sum) time complexity】

In this article, we will solve this using a dynamic programming approach which will take O(N * sum) time complexity which is significantly faster than the other approaches which take exponential time.

Algorithms

Shortest Common SuperSequence 【O(M*N) time complexity】

Given two strings X and Y, the supersequence of string X and Y is such a string Z that both X and Y is subsequence of Z.

Algorithms

Word Break Problem 【O(n * s) time complexity】

In this problem we are given with a string and a dictionary of words, we need to find if the string can be segmented to words so that all the segmented words are present in the dictionary.

Algorithms

Find the maximum sum bitonic subsequence

Given a sequence of numbers in an array A[0.......N]. Find the sum of the maximum bitonic subsequence in the array. naive algorithm will take exponential time O(N * (2^N)) but we can reduced it to O(N^2) using Dynamic programming. We will explore naive approach and go into the dynamic programming

Algorithms

Count paths from Top Left to Bottom Right of a Matrix using Dynamic Programming【O(M*N)】

Count all the possible paths from top left to bottom right of a m x n matrix with the constraints that from each cell you can either move only to right or down. Brute force approach takes exponential time while dynamic programming takes O(M*N) time complexity

Algorithms

Solving Vertex Cover Problem from O(2^n) to O(n^2)

Vertex Cover Problem is a known NP Complete problem. We will see Naive approach and Dynamic programming approach to solve the vertex cover problem for a binary tree graph and reduce the complexity from O(2^n) to O(n^2).

Algorithms

Number of unique partitions of an integer

Given a positive integer, the problem is to find all the Unique Partitions of the number. We can understand the above problem using some basic examples. Naive approach takes O((N^N)log N) time complexity while Dynamic programming takes O(2^N)

Algorithms

Number of non unique Partitions of an Integer

The problem is to find number of non unique partitions of an integer. To solve this problem, we will explore naive approach O(N^N), Dynamic programming approach O(N^2) and Optimal approach O(log N)

Algorithms

Tile Stacking Problem

We demonstrate how we will reduce the time complexity from O((k+1)^(m+1)) to O(N * M * K) to O(N * M). We have infinite number of tiles of sizes 1 to m. The task is calculate the number of different stable tower of height n with restriction that you can use at most k tiles of each size in the tower

Algorithms

Binary Lifting with k-th ancestor and lowest common ancestor (LCA)

Binary Lifting is a technique used to find the k-th ancestor of any node in a tree in O(log N). This also leads to a faster algorithm in finding the lowest common ancestor (LCA) between two nodes in a tree. The technique requires preprocessing the tree in O(N log N) using dynamic programming.

Dynamic Programming (DP)

Longest Bitonic Sequence

The problem we will solve is given a sequence an array of positive integers and have to find the length of longest bitonic subsequence. Using dynamic programming ideas, we will solve this on O(N^2) time complexity

Algorithms

Number of arithmetic progression subsequences in a given set of numbers

The problem is that given an array of n positive integers. The task is to count the number of Arithmetic Progression subsequence in the array. This can be solved using dynamic programming in linear time complexity.

Algorithms

Find the Longest Arithmetic Progression using Dynamic Programming

The problem we will solve is that given a set of integers in sorted order, find length of longest arithmetic progression in that set. This can be solved by brute force in O(N^3) while a dynamic programming approach with take O(N^2) time complexity.

Algorithms

Manacher's Algorithm

Manacher's Algorithm is an efficient algorithm to find the longest palindromic substring in a given string in linear time and linear space complexity. It uses key ideas from dynamic programming to solve the problem efficiently.

Algorithms

The Coin Change Problem

Given a set of coins S with values { S1, S2, ..., Sm }, find the number of ways of making the change to a certain value N. There is an infinite quantity of coins and the order of the coins doesn't matter. This real life problem can be solved by Dynamic Programming in

Dynamic Programming (DP)

Box stacking Problem

Given a set of n types of 3D rectangular boxes, find the maximum height that can be reached stacking instances of these boxes. This problem can be solved efficiently by using Dynamic programming in O(N^2) time complexity and linear O(N) space complexity.

Dynamic Programming (DP)

0-1 Knapsack Problem (Integral Knapsack)

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Brute force approach will take exponential time while a dynamic programming approach will take linear time.