List of Dynamic Programming (DP) 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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

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.

Algorithms

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.

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.

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.