The Dynamic Programming Technique #1

                 Dynamic Programming (Part 1) 

  Dynamic Programming is a powerful technique that could help us solve many difficulty problems. It break down a problems into sub-problems then solve it accordingly. In general, a dynamic programming algorithm will examine the previously solved subproblems and combine their solutions to give the best solution for the given problem.

Here are 4 key steps for every dynamic programming problem:

1. Define the dynamic programming table.

2. Initialize values in the table.

3. Use recurrence to fill the table

4. Get the solution.

Let's go ahead and solve some problems using this powerful weapon  !

         1 . Coin change 

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

------------------------------------------------------------------------------------------------------------------------------------------------------

Analyze:  We will do this problem step by step according to the 4 key steps of dynamic programming.

1.  We define our table dp[i] = number of ways we can find change, if the given value is i. So the final answer will be in dp[N].

2. Initialize the table: If given amount is 0, then we will give no coin at all as a answer. So dp[0] = 1.

3. The recurrence relation: if we have a coin that value = j . and want to update dp[i], then dp[i] += dp[i-j]  ( i>=j)

Because if we have n ways to make change to (i-j), we just need to add one j coin to those ways and we will get same ways to amount i.

4. After we doing that for every coin we have, we will get our final answer in dp[N].

Here is the solution based on those 4 steps:

So the code in Line 8 to 10 means, we do it for every coin we have and update value from its its amount j, until the final amount we interested in, which is variable amount in this example.

         2. Coin Change II 

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:

You may assume that you have an infinite number of each kind of coin.

------------------------------------------------------------------------------------------------------------------------------------------------------

Analyze :

1. We define table dp[i] will be the Min number of coins that we need to give when amount is i.

2. For the value 0, we will not give any coin so dp[0] = 0 ;

3. if we have a coin value is j, and we want to know dp[i] ( i>=j), dp[i] = Math.Min(dp[i], dp[i-j]), because we can add one coin in  dp[i-j] previous answer stored in our table , or we do not update it because it will not give us a better solution.

4. The result will be in dp[amount], if we have a solution for it.

Note that the condition in Line 11 means, we only update this value if we have a solution to get (j-coin[i]).

         3. Decode ways 

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

--------------------------------------------------------------------------------------------------------------------------

Analyze:

1. Define table dp[i] will store the number of ways we can decode this string for s.substring(0,i)

2. Initialize the table dp[0] = 1, and if the first number is not 0, we will have one way to decode it

3. we look back one position get number k, if  (1<=k<=9) we will add dp[i-1] to current dp[i]

   look back two position get number g if ( 1<= g <= 26), we will add dp[i-2] to current dp[i]

4. The result is in dp[s.length()].

Note: Any number start with 0 is invalid number because our encoding system is from 1 to 26.

Hope it helps you master DP :-)

Happy Coding^^

Ye Jiang