## Rod Cutting Problem

Given a rod of length n and list of prices of rod of length i where 1 < = i

## Find all N-digit binary strings without any consecutive 1’s

Given a positive integer N, count all N-digit binary strings without any consecutive 1’s.

## Subset Sum Problem

Given a set of positive integers and an integer s, is there any non-empty subset whose sum to s.

## Partition problem | Dynamic Programming Solution

Given a set of positive integers, find if it can be divided into two subsets with equal sum.

## Maximize the Value of an Expression

Given an array A, maximize value of the expression (A[s] – A[r] + A[q] – A[p]) where p, q, r and s are indices of the input array and s > r > q > p.

## 0-1 Knapsack problem

In 0-1 Knapsack problem, we are given a set of items, each with a weight and a value and we need to determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as …

## Find the minimum cost to reach last cell of the matrix from its first cell

Given a M x N matrix where each cell has a cost associated with it, find the minimum cost to reach last cell (M-1, N-1) of the matrix from its first cell (0, 0). We can only move one unit right or one unit down from any cell. i.e. from cell (i, j), we can …

## Matrix Chain Multiplication using Dynamic Programming

Matrix chain multiplication problem: Determine the optimal parenthesization of a product of n matrices.

## Find size of largest square sub-matrix of 1’s present in given binary matrix

Given a M x N binary matrix, find the size of largest square sub-matrix of 1’s present in it.

## The Levenshtein distance (Edit distance) problem

Edit distance is a way of quantifying how dissimilar two strings are to one another by counting the minimum number of operations required to transform one string into the other.

## Increasing Subsequence with Maximum Sum

Find a subsequence of a given sequence such that subsequence sum is as high as possible and subsequence’s elements are in sorted order, from lowest to highest. This subsequence is not necessarily contiguous, or unique.

## Longest Bitonic Subsequence

The longest bitonic subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are first sorted in in increasing order, then in decreasing order, and the subsequence is as long as possible.