List of Dynamic Programming problems

Find the number of subsets of an array having a given XOR value

We are given an array of size N and a value M, we have to find the number of subsets in the array having M as the xor value of all elements in the subset. This can be solved using Dynamic Programming in linear time.

algorithm

Longest repeating and non overlapping substring in a string

We have to find the longest repeating and non-overlapping substring in a given string. Brute force approach takes O(N^3) time while Dynamic Programming takes O(N^2) time.

algorithm

Shortest Path with k edges using Dynamic Programming

Given a weighted directed graph, we need to find the shortest path from source u to the destination v having exactly k edges. Brute force approach takes O(V^k) time complexity which we reduce to O(V^3 * k) using dynamic programming

algorithm

Number of paths with k edges using Dynamic programming and Divide and Conquer

Given a directed graph, we need to find the number of paths with exactly k edges from source u to the destination v. A brute force approach has time complexity which we improve to O(V^3 * k) using dynamic programming which we improved further to O(V^3 * log k) using a divide and conquer technique.

algorithm

Number of ways to pair elements

In this article, we are going to discuss about element pairing problem where we need to find the number of ways a set of elements can be pair or kept separate. This can be solved using Dynamic Programming in linear time O(N).

algorithm

Break a number in 3 parts (n/2, n/3, n/4) recursively to get maximum sum

Given a number n, we can divide it in only three parts n/2, n/3 and n/4 recursively and find the maximum sum of the 3 parts. This can be solved in linear time using Dynamic Programming

algorithm

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.