Category: Dynamic Programming

Longest Increasing Subsequence using LCS

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.  

Word Break Problem | Dynamic Programming

Word Break Problem: Given a string and a dictionary of words, determine if string can be segmented into a space-separated sequence of one or more dictionary words.

Find optimal cost to construct Binary Search Tree

Find optimal cost to construct binary search tree where each key can repeat several times. We are given frequency of each key in same order as corresponding keys in inorder traversal of a binary search tree.

Longest Alternating Subsequence Problem

Longest Alternating Subsequence is a problem of finding a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence is as long as possible.

Maximum Product Rod Cutting

Given a rod of length n, find the optimal way to cut rod into smaller rods in order to maximize product of price of each of the smaller rod. Assume each rod of length i has price i.

Rod Cutting Problem

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