Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler sub problems. If the sub problems have solution save the result for future reference to avoid solving the same problem again. The dynamic programming can be achieved in two ways. The top down approach memorize the solution for every step. The bottom approach build tabular form and iteratively generate solutions to bigger and bigger sub-problems by using the solutions to small sub-problems. Example finding the shortest path between two points, or the fastest way to multiply many matrices
 212 LRU cache Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. 213 String matching Write a program for String matching 214 Fibonacci numbers Fibonacci number is a number that start with one or zero and next number is equal to the sum of previous two numbers. Ex F (0) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. 215 Rod cutting Write a program to find the maximum value obtainable by cutting up the Rod and selling the pieces. The Rod length N and an array of prices that contains prices of all pieces of the size smaller than n. 216 Matrix multiplication Write a program to multiply matrix using Dynamic programming 217 Optimal Binary search tree A binary search tree is a binary tree which provides the smallest possible search time for a given sequence of accesses. 218 Longest common subsequence Longest common subsequence (LCS) is a problem that uses for finding the longest subsequence common to all sequences in a set of sequences 219 Dice Throw Problem Find the number of ways to get the summation of values on each face when all dice thrown. We have N dice with M faces. 220 Coin Change Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, n, using a given set of denominations d{1} dots d{m}. 221 Subset Sum Problem Given a set of integers, is there a non-empty subset whose sum is zero? For example, given the set {-7, -3, -2, 5, 8}, the answer is yes because the subset {-3, -2, 5} sums to zero. 223 Maximum Value Contiguous Subsequence Write a program to find the sum of subarray within a one-dimensional array of numbers which has the largest sum. 224 Edit Distance 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.