×
Home Discussions Write at Opengenus IQ
×
  • #7daysOfCode
  • C Interview questions
  • Linux 💽
  • 🔊 Data Structures
  • Graph Algorithms
  • Dynamic Programming 💑
  • Greedy Algo 📔
  • Algo Book 🧠
  • String Algo 🧬
  • Join our Internship 🎓
  • Home

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

Algorithms

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.

Amruta U. Koshe
Algorithms

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.

Shalini Jaiswal
Algorithms

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.

Aarushi Ghadiya
Algorithms

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

Ayush Mehar
Algorithms

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.

Sweta Behera
Algorithms

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.

K. Sai Drishya K. Sai Drishya
Algorithms

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.

Raghav Somani
Algorithms

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.

Abhijit Tripathy Abhijit Tripathy
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.

Anand Saminathan
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.

Anand Saminathan
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.

Priya Raut Priya Raut
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.

Shweta Bhardwaj
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.

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

K. Sai Drishya K. Sai Drishya
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.

Reetika Poosarla
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.

Shujaa Ahmad Shujaa Ahmad
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.

K. Sai Drishya K. Sai Drishya
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.

K. Sai Drishya K. Sai Drishya
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.

Shubham Kumar Shubham Kumar
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.

Shubham Kumar Shubham Kumar
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.

K. Sai Drishya K. Sai Drishya
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.

Siddharth Agarwal Siddharth Agarwal
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.

Abhiram Reddy Duggempudi Abhiram Reddy Duggempudi
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

Ashutosh Singh Ashutosh Singh
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.

Ashutosh Singh Ashutosh Singh
×

Visit our discussion forum to ask any question and join our community

View Forum
OpenGenus IQ © 2021 All rights reserved â„¢ [email: team@opengenus.org]
Top Posts LinkedIn Twitter