×

Home Discussions Write at Opengenus IQ

×

Dynamic Programming (DP)

Dynamic Programming is an algorithmic technique in which the key idea is to store the values of smaller problems such that in case, the value is required again, it will return the value instead of recomputing. This works in problems which can be broken into smaller problems and smaller problems are encountered multiple times. When applicable, dynamic programming can reduced the time complexity greatly

Boolean Parenthesization Problem

We will solve Boolean Parenthesization Problem using Dynamic Programming and understand the algorithm with a step by step explanation. The time complexity to solve this problem is O(N^3) with a space complexity of O(N^2).

Dynamic Programming (DP)

Longest Palindromic Subsequence (using Dynamic Programming)

Longest palindrome subsequence problem (LPS) is the problem to find the length of longest subsequence in a string that is a palindrome. This can be done using Dynamic Programming in O(N^2) time.

Assembly Line Scheduling using Dynamic Programming

The main goal of solving the Assembly Line Scheduling problem is to determine which stations to choose from line 1 and which to choose from line 2 in order to minimize assembly time. We solve this using Dynamic Programming.

Dice Throw Problem (Dynamic Programming)

There are d dice each having f faces. We need to find the number of ways in which we can get sum s from the faces when the dice are rolled. We have explored a Dynamic Programming solution to Dice Throw problem.

Maximum Sum Decreasing Subsequence (Dynamic Programming)

Given an array of n positive integers, find the sum of the maximum sum decreasing subsequence (msds) of the given array such that the integers in the subsequence are sorted in decreasing order.

Longest Decreasing Subsequence using Dynamic Programming

In this problem (Longest Decreasing Subsequence), you are given an array of length N. You have to find the longest decreasing subsequence (LDS) from the given array. We have solved this using Dynamic Programming.

Longest Common Decreasing Subsequence

In this problem (Longest Common Decreasing Subsequence), we are given 2 arrays and we need to find out the longest common decreasing subsequence from those two arrays. This can be solved using Dynamic Programming.

Maximum Sum Increasing Subsequence

In this problem (Maximum Sum Increasing Subsequence), we are given an array and we need to find out the maximum sum increasing subsequence from that array. This can be solved using Dynamic Programming.

Diameter of N-ary tree using Dynamic Programming

We are given input as the reference to the root of an N-ary tree. We need to calculate the diameter of the tree that is the longest path between any two nodes using Dynamic Programming.

Set Partition Problem (Same sum)

Set Partition Problem: determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same. The time complexity of solving this using Dynamic Programming takes O(N x SUM) time.

Wildcard Pattern Matching (Dynamic Programming)

In the Wildcard Pattern Matching problem, we find if a pattern matches a given input string. We will be using a Dynamic Programming approach with the time complexity of O(m * n), here m and n represent length of string and pattern respectively.

Number of substrings in a string divisible by 6

Given a string of integers, find the count of sub-strings of given string which are divisible by 6. This problem can be solved using Dynamic Programming in O(N) time complexity where N is the length of the string.

Word Break Problem

In this article we are going to talk about a very interesting problem: Word Break Problem. This can be solved using Dynamic Programming [O(N^2) time, O(N^2) space].

Find path with maximum average value in a 2D matrix

Given a square matrix of size N * N, where each cell is associated with a specific cost. Find the path with maximum average value in the 2D matrix. The path should start from top left point and end at bottom right point.

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

In this problem, we are given a number, we need to find the number of ways to reach it using increments of 1 and 2, given consecutive 1s not allowed.

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.

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.

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.

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.

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.

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.

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

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.

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.