# Dynamic Programming

The most difficult problems in Coding competitions and interviews of companies like Google, Microsoft etc. are from Dynamic Programming. DP as an approach to problem solving is discussed in almost all algorithm books. But, in most of the books, DP, as a concept is lost behind the difficult problems. For example, in one of the best […]

Given two strings of size m and n respectively, find the minimum number of operations required to transform one string into another. The following thee operations are allowed Insert(pos, ch) – Insert a character at a position in the string. Delete(position) – Delete a character from a position in the string. Replace(position, character) – Replace […]

Given an array of integers, write a function that returns true if it can be divided in two parts having equal sum. For example: If Input array is {10, 20 , 30 , 5 , 40 , 50 , 40 , 15} Output: true Divide the array in two parts {0, 20, 30, 5, 40} […]

The basic idea of DP is applicable to problems that can be thought in terms of recursion. For example, consider problem of computing n’th fibonacci term:

Write a C function to compute xn which uses minimum number of multiplications. unsigned int power(double x, unsigned int n)

Given an array of n integers (both +ve and -ve). Find the contiguous sub-array whose sum is maximum (More than 1 sub-array may have same sum). For Example: Array Maximum Sub-Array sum ———————– ———————– —- {5, 7, 12, 0, -8, 6} {5, 7, 12} 24 {6, -2, -3, 4, -1, 10 } {6, -2, -3, […]