List of Dynamic Programming (DP) problems

Smallest sum contiguous subarray

You are given an array of n integers. The task is to find the sum of the subarray which has the smallest possible sum.

Travelling Salesman Problem (Bitmasking and Dynamic Programming)

In this article, we will start our discussion by understanding the problem statement of The Travelling Salesman Problem perfectly and then go through the basic understanding of bit masking and dynamic programming.

Algorithms

Divide and Conquer Optimization in Dynamic Programming

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.

Algorithms

Knuth's optimization in Dynamic Programming

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.

Algorithms

Maximum houses a Robber can rob

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.

Algorithms

Number of substrings divisible by 8 but not 3

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.

Algorithms

Minimum number of increment or decrement (by 1) operations to make array in increasing order

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.

Algorithms

Number of ways to reach a number using increments of 1 and 2 (consecutive 2s are not allowed)

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

Algorithms

Partition a set into two subsets such that sum of each subset is same

An analysis and explanation of the solution for the partition problem, in which a set of numbers is to be divided into two sub arrays such that their sum is equal, by using dynamic programming.

Algorithms

Minimum number of characters to be deleted to make string a palindrome

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.

Algorithms

Longest Palindromic Substring using Dynamic Programming

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.

Algorithms

Number of ways to reach a given number using increments of 1 and 2

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.

Algorithms

Find the Longest Increasing Odd Even Subsequence

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.

Algorithms

Find the Longest Common Increasing Subsequence

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.

Algorithms

Maximum product cutting problem

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.

Algorithms

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

Algorithms

Find minimum number of deletions to make a string palindrome

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.

Algorithms

Longest Common 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

Algorithms

Longest Common Substring in two strings

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.

Algorithms

Rod cutting problem

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

Algorithms

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.

Algorithms

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.

Algorithms

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

Algorithms

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.

Algorithms

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