Dynamic Programming (DP)

In this article, we have explored the longest palindromic substring problem for which brute force takes O(N^3) time while a Dynamic Programming approach takes O(N^2) time.

The problem we will try to solve is to find the Number of ways to reach a given number (or a score in a game) using increments of 1 and 2 with consecutive 1s and consecutive 2s allowed. This is solved in linear time O(N) using Dynamic Programming.

In this problem, we have formulated an algorithm to find the Longest Increasing Odd Even Subsequence. Brute force approach takes exponential time O(2^N) but a Dynamic Programming approach takes O(N^2) time.

In this problem, we have formulated an algorithm to find the Longest Common Increasing Subsequence. Brute force approach takes exponential time but a Dynamic Programming approach takes O(N^2) time.

In Maximum product cutting problem. we are given a rod of length N which we need to cut into small pieces such that the product of the length of the pieces is maximum. This is similar to the Rod Cutting problem and can be solved using Dynamic Programming.

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 Bitwise OR value of all elements in the subset. This can be solved using Dynamic Programming in polynomial time.

We need to find the minimum number of characters to be deleted in a string to make it a palindrome. This can be done in O(N^2) time with the help of Dynamic Programming approach of Longest Palindromic Subsequence.

In this problem, we solved the Longest Common Subsequence problem using Dynamic Programming which takes O(N*M) time while a brute force approach takes O(2^N) time

In this problem, we explored a Dynamic Programming approach to find the longest common substring in two strings which is solved in O(N*M) time. Brute force takes O(N^2 * M) time.

In this article, we explored the rod cutting problem in depth which can be solved using a Dynamic Programming approach that takes O(N^2) time and O(N) space

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.

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

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

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.

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

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

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

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

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