dynamicProgrammingProblemSetOct2.md

Dynamic Programming 2018 Oct 2

Problem Set

Fibonacci

• I want to find a Fibonacci sequence for an integer.
• The Fibonacci for n is the sum of the Fibonaccis of the previous two numbers.
• Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
• Solution: O(N) where N is the value of the integer

Finding the edit distance between two strings

The Levenshtein distance is a measure of dissimilarity between two Strings.  Mathematically, given two Strings x and y, the distance measures the minimum number of character edits required to transform x into y.

Typically three type of edits are allowed:

1. Insertion of a character c
2. Deletion of a character c
3. Substitution of a character c with c‘

Example: If x = ‘shot’ and y = ‘spot’, the edit distance between the two is 1 because ‘shot’ can be converted to ‘spot’ by substituting ‘h‘ to ‘p‘.

Solution: O(N*M) where N and M are the lengths of the two strings

Robbery

• There are n houses build in a line, each of which contains some value in it.
• A thief is going to steal the maximal value of these houses, but he can’t steal in two adjacent houses because owner of the stolen houses will tell his two neighbour left and right side.
• What is the maximum stolen value?

Input  : hval[] = {6, 7, 1, 3, 8, 2, 4}
Output : 19
Thief will steal 6, 1, 8 and 4 from house.

Input  : hval[] = {5, 3, 4, 11, 2}
Output : 16
Thief will steal 5 and 11

Solution: O(N) where N is the number of houses

Minimum number of coins to make change

Find minimum number of coins that make a given value Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, .. , Cm} valued coins, what is the minimum number of coins to make the change? Examples:

Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents 

Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents

Optimal Strategy for Game

• Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.

Note: The opponent is as clever as the user.

Examples

   1. 5, 3, 7, 10 : The user collects maximum value as 15(10 + 5)
   2. 8, 15, 3, 7 : The user collects maximum value as 22(7 + 15)