×

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

Egg Dropping Puzzle

In this article, we have explored the Egg Dropping Puzzle in depth with various algorithms including Combinatorics and Dynamic Programming.

Dynamic Programming (DP)

Longest Geometric Progression

In this article, we have explained how to solve the problem of Longest Geometric Progression efficiently using Dynamic Programming. It involves the use of Map data structure in implementation which is different from other standard problems.

Dynamic Programming (DP)

Longest Increasing Subsequence [3 techniques]

In this article, we have explained the problem of Longest Increasing Subsequence along with 3 techniques (Brute force, Binary Search, Dynamic Programming).

Dynamic Programming (DP)

Word Wrap Problem

In this article, we have solved the Word Wrap Problem in depth. This involves Dynamic Programming Concepts.

Compiler Design

Dynamic programming for Code generation

Dynamic programming not only applies to a broad class of register machines but its application results in the generation of optimal code that runs in linear time.

Maximum size square submatrix with all 1s

In this article, we have explored various ways to solve the problem of finding maximum size square submatrix with all 1s. This can be solved using Dynamic Programming.

Dynamic Programming (DP)

Dynamic Programming on Trees

In this article, we have explored the idea of Dynamic Programming on Trees in depth and presented some practice problems.

Jump Game II: Minimum number of jumps to last index

In this post, we will explore various ways to solve the minimum number of jumps to last index (Jump Game II) problem. In this, we will use ideas of Dynamic Programming and Greedy Algorithm.

Shortest Superstring problem

In this article, we have explained three approaches to solve the Shortest Superstring problem. This involve concepts like DFS and Dynamic Programming.

Longest Increasing Consecutive Subsequence

We have to find the Longest Increasing Consecutive Subsequence in N elements. We can solve this problem efficiently using Dynamic Programming in O(N) time.

Karp's Minimum Mean Cycle Algorithm

We have presented Karp's Minimum Mean Cycle Algorithm along with C++ Implementation. Karp's theorem and Complexity Analysis.

Dynamic Programming (DP)

List of 100+ Dynamic Programming Problems

This is the List of 100+ Dynamic Programming Problems along with different types of DP problems such as Mathematical DP, Combination DP, String DP, Tree DP, Standard DP and Advanced DP optimizations.

How to approach Dynamic Programming problems? (with example)

We have explained How to approach a Dynamic Programming problem with an example. The approach depends on the constraints of the problem at hand.

Number of expressions that evaluate to value K

In this problem, we have to form expressions using + and - and find the number of expressions that evaluate to K. This can be solved efficiently using Dynamic Programming and is an extension of Count Subset Problem.

String Algorithms

Number of palindromic substrings in a string

A string is a palindrome when it reads the same backward as forward and a substring is a contiguous sequence of characters within the string. We have discussed multiple approaches to find the number of palindromic substrings in a given string.

Minimum number of nodes to be removed such that no subtree has more than K nodes

The article contains editorial + implementation for Finding minimum number of nodes to be removed such that no sub tree has more than K nodes.

Number of substrings with exactly k distinct characters

In this problem, we are given a string and our job is to count the total number of substrings of the given string that contains exactly k distinct characters. We have explored 3 approaches to solve this.

Longest Alternating Subsequence

Given an array, find the length of the longest alternating subsequence. We solve this using two approaches: Dynamic Programming and Efficient Approach.

Find length of the longest Fibonacci subsequence

We have a strictly increasing array of positive integers. Our task is to find the length of the longest Fibonacci subsequence possible. We will solve this using Brute force and Dynamic Programming.

Coin Change Problem

Coin change problem is very similar to unbounded knapsack problem which can be solved easily and efficiently by using Dynamic Programming. General task is to find maximum number of ways to add the coins from the array for given amount.

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.