List of Dynamic Programming (DP) problems

Interleaving String [Solved]

The Interleaving Strings problem is a classical dynamic programming problem that involves whether a string can be formed by interleaving two strings. In this article, we'll explore this problem in depth and provide a C++ implementation using dynamic programming.

Algorithms

Greedy Algorithm vs Dynamic programming

In this article, we will discuss greedy methods vs dynamic programming. Both of them are used for optimization of a given problem. Optimization of a problem is finding the best solution from a set of solutions.

Algorithms

3D Kadane's algorithm

In this article we are going to learn about what kadane's algorithm is and will also see how to apply it on 3-dimensional arrays to generate a sub-cube with maximum sum of its elements (3D Kadane's algorithm).

binary search

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.

Algorithms

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.

Algorithms

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.