List of Dynamic Programming problems

Largest subset with divisible pairs

We explored the method to get the longest subset within any given array, such that for each pair, the smaller number divides the larger number using Dynamic Programming.

algorithm

Calculate Binomial Coefficient using Dynamic Programming

Using a recursive relation, we will calculate the N binomial coefficient in linear time O(N * K) using Dynamic Programming

algorithm

Maximum Sum Rectangle in a Matrix

Given a 2D array, we need to find the subarray with the maximum sum of its elements. We solve this using Dynamic Programming in O(N^3) where brute force takes O(N^5)

algorithm

Calculate Newman Conway Sequence

Newman Conway Sequence is the sequence which follows a given recursive relation (p(n) = p(p(n-1)) + p(n-p(n-1))). We solve it using Dynamic Programming in O(N) time

algorithm

Find number of subsets with sum divisible by given number M

Find the number of subsets with sum divisible by given number M. We solved this using a Dynamic Programming approach with time complexity O(N * M).

algorithm

Finding the number of sub matrices having sum divisible by K

This article is about counting the number of sub-matrices such that the sum of the elements is divisible by k and using Dynamic Programming, we solve it in O(N^3)

algorithm

Number of ordered pairs such that (A[i] & A[j])=0

Given array A[] of n integers, find out the number of ordered pairs such that (A[i]&A[j])=0. This can be done using dynamic programming in O(N*(2^N)) time

algorithm

Largest rectangular sub matrix having sum divisible by k

This article is about finding the size of the largest area of the rectangular sub-matrix such that the sum of the elements is divisible by k.

algorithm

Calculating Permutation Coefficient

Given n and k, we will calculate permutation coefficient using dynamic programming in O(N * K) time complexity.

algorithm

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.

algorithm

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

algorithm

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

algorithm

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

algorithm

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.

algorithm

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.

algorithm

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.

algorithm

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.

algorithm

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.

algorithm

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.

algorithm

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.

algorithm

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

algorithm

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

algorithm

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).

algorithm

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)

algorithm

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)