Dynamic Programming (DP)

Divide and conquer optimization is used to optimize the run-time of a subset of Dynamic Programming problems from O(N^2) to O(N logN). We have demonstrated it with an example.

Knuth's optimization is used to optimize the run-time of a subset of Dynamic programming problems from O(N^3) to O(N^2). We have explained this with a sample problem.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money the robber can rob tonight without alerting the police. We have solved this problem using Dynamic Programming.

We need to find total number of substrings that are divisible by 8 but not 3 in the given string. We have solved this problem using Dynamic Programming in linear time O(N) where the brute force approach takes O(N^2) time.

Given an array of size N. Find the minimum number of increment or decrement operations to make the array in increasing order. In each move, we can add or subtract 1 to any element in the array.

The problem states that given a number or a score, we need to find the number of ways to reach it using increments of 1 and 2 with a constraint that consecutive 2s aren't allowed. We will solve this using Dynamic Programming in linear time O(N).

In this problem, we have to formulate an algorithm to find the minimum number of characters to be deleted to make the string a palindrome. This can be solved using the Dynamic Programming approach for longest palindromic subsequence in O(N^2) time.

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.