Category Archives: Dynamic Programming

Matrix Chain Multiplication

Matrix Chain Multiplication – Dynamic Programming Matrix Chain Multiplication Problem Statement: Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]. We need to write a function MatrixChainOrder() that should return the minimum number of multiplications needed to multiply the chain. The problem… Read More »

Largest Sum Contiguous Subarray

Largest Sum Contiguous Subarray (Kadane’s Algorithm) – Dynamic Programming (Maximum Sum Subarray Problem) Largest Sum Contiguous Subarray Problem Statement: Given an array, we need to find the a subarray (contiguous) which has the maximum sum and print the value of its sum. Maximum Subarray Problem Example: a[] = {-2, -3, 4, -1, -2, 1, 5, -3}… Read More »

Coin Change Problem

Coin Change Making – Dynamic Programming Coin Change Making Problem Statement: Given a value N in some currency, we want to make change for N using given different coins of given values,how many ways can we make the change? Note: The order of coins doesn’t matter. and we have infinite supply of each of given  valued coins… Read More »

Longest Palindromic Subsequence using LCS

Longest Palindromic Subsequence using Longest Common Subsequence (LCS) – Dynamic Programming. Longest Palindromic Subsequence Problem Statement: Given a sequence, find the length of the longest palindromic subsequence in it. For example, if the given sequence is “AGBDBAH”, then the output should be 5 as “ABDBA” is the longest palindromic sub-sequence in it. “BDB” is also palindromic… Read More »

Longest Common Subsequence

Longest Common Subsequence (LCS) – Dynamic Programming Longest Common Subsequence Problem Statement: Given two sequences (strings or arrays) A and B, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “coe”, “ksa”, “dek”, “code”, ‘”kaksa”,… Read More »

Longest Bitonic Subsequence

Longest Bitonic Subsequence. Maximum Length Bitonic Subsequence- Dynamic Programming. Longest Bitonic Subsequence Problem Statement : Given an array of N integers, we need to find the length of the maximum length bitonic Subsequence. Bitonic Subsequence: It is a sequence of numbers that are first increasing then decreasing. Note: A sequence, sorted in increasing order is… Read More »

Maximum Sum Increasing Subsequence

Maximum Sum Increasing Subsequence (MSIS) – Dynamic Programming. Given an integer array, find the subsequence of numbers from  the array such that all numbers of the subsequence are sorted in increasing order and have the maximum sum among all such subsequence. Maximum Sum Increasing Subsequence Example: {4, 6, 1, 3, 8, 4, 6} is the input… Read More »

Minimum Cost Path

Minimum(or maximum) Cost Path – Dynamic Programming. Minimum Cost Path Problem Statement: Given a 2-D array, with the value of each element be equal to the cost that is associated with each block. We need to find the minimum cost of traversing the matrix from (0,0) to (M,N). Given that the allowed moves from a… Read More »

0-1 Knapsack Problem

0-1 Knapsack Problem – Dynamic Programming. 0-1 Knapsack Problem Statement: Given N items, their respective weight and profit and a knapsack of capacity W. We need to select items to be put in the knapsack such that we maximize the profit gained and do not exceed the capacity of knapsack. The problem is called 0-1… Read More »

Box Stacking Problem

Box Stacking Problem (using LIS). Box Stacking Problem Statement: Given N 3-D cuboid-al boxes  all with different Height Width and Depth. We have to make a tower of maximum height using these boxes such that both the dimensions of the box stacked above are smaller than that of the box on which it is stacked.… Read More »