List of Dynamic Programming problems

Tile Stacking Problem

We demonstrate how we will reduce the time complexity from O((k+1)^(m+1)) to O(N * M * K) to O(N * M). We have infinite number of tiles of sizes 1 to m. The task is calculate the number of different stable tower of height n with restriction that you can use at most k tiles of each size in the tower

algorithm

Binary Lifting with k-th ancestor and lowest common ancestor (LCA)

Binary Lifting is a technique used to find the k-th ancestor of any node in a tree in O(log N). This also leads to a faster algorithm in finding the lowest common ancestor (LCA) between two nodes in a tree. The technique requires preprocessing the tree in O(N log N) using dynamic programming.

dynamic programming

Longest Palindromic Subsequence: Reducing complexity from O(2^N) to O(N^2)

The longest palindrome subsequence problem (LPS) is the problem to find longest subsequences of a string that is also a palindrome. We will see two solutions one which is a naive solution and the other is a dynamic programming approach where we will reduce the time complexity from O(2^N) to O(N^2)

dynamic programming

Longest Bitonic Sequence

The problem we will solve is given a sequence an array of positive integers and have to find the length of longest bitonic subsequence. Using dynamic programming ideas, we will solve this on O(N^2) time complexity

algorithm

Number of arithmetic progression subsequences in a given set of numbers

The problem is that given an array of n positive integers. The task is to count the number of Arithmetic Progression subsequence in the array. This can be solved using dynamic programming in linear time complexity.

algorithm

Find the Longest Arithmetic Progression using Dynamic Programming

The problem we will solve is that given a set of integers in sorted order, find length of longest arithmetic progression in that set. This can be solved by brute force in O(N^3) while a dynamic programming approach with take O(N^2) time complexity.

string algorithm

Manacher's Algorithm

Manacher's Algorithm is an efficient algorithm to find the longest palindromic substring in a given string in linear time and linear space complexity. It uses key ideas from dynamic programming to solve the problem efficiently.

dynamic programming

The Coin Change Problem

Given a set of coins S with values { S1, S2, ..., Sm }, find the number of ways of making the change to a certain value N. There is an infinite quantity of coins and the order of the coins doesn't matter. This real life problem can be solved by Dynamic Programming in

dynamic programming

Box stacking Problem

Given a set of n types of 3D rectangular boxes, find the maximum height that can be reached stacking instances of these boxes. This problem can be solved efficiently by using Dynamic programming in O(N^2) time complexity and linear O(N) space complexity.

dynamic programming

0-1 Knapsack Problem

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

catalan number

Catalan Numbers

Catalan Numbers are one of the widest used and evident number patterns. They are named after the Belgian mathematician Eugène Charles Catalan. A sequence of natural numbers that occur in various counting problems. The Catalan numbers are: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,

graph algorithm

Floyd-Warshall Algorithm: Shortest path between all pair of nodes

Floyd-Warshall Algorithm is an algorithm based on dynamic programming technique to compute the shortest path between all pair of nodes in a graph. The credit of Floyd-Warshall Algorithm goes to Robert Floyd, Bernard Roy and Stephen Warshall.