The Dynamic Programming Technique #2

                                                           

             Dynamic Programming (Part 2) 

   After the first part discussion of Dynamic Programming, we may have a foretaste of the power of dynamic programming. Actually, it can solve some problem in O(N^2) or better ,where other approaches may need O(N!) time and, for the most of the time, the key to dynamic programming is just finding the recurrence relationship.

   I hope following 3 examples can make use more solid in using Dynamic Programming to solve problems and add more appreciation of its elegance. Analyze

            1. Max Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

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

Analyze: Is "Max Subarray" looks  somewhat familiar to you ?  Well, if you read the Sliding Window Algorithm  I wrote before, you may still remember Sliding window algorithm is used to solve optimal subarray and substring problem. So, Can we use Sliding window algorithm to solve this max subarray problem ?  

 Recall that in the sliding window algorithm we change the window size while the sub-array inside that window still have certain properties we want. However, we do not really have some properties we need to satisfy in this problem. Besides, because there are  negative values in the array so the window size does not necessarily indicate  the decreasing or increasing  of total sum of this sub-array.  As a result, we can not use sliding window algorithm to solve this problem,  but the analyzing process is very crucial.

 Then we try to use Dynamic Programming to solve it.

1. The first question will be how do you define your table. You may try something like dp[i] the max subarray until position i. However, that approach is not gonna work.( you can try it out by yourself) and we define our table dp[i] be the max subarray that must contain array[i] element.

2. The first position dp[0] = A[0].

3. The recurrence relation is  dp[i] = Math.max(A[i],A[i]+dp[i-1]); which means we either extend previous result make this subarray longer by add this position in the end, or we just start from this current position ( because previous result may be negative ).

4. As we do not know what elements will be contained in this sub-array, so we can not get our final result from a specific position of our table, but the final result will at least appeared once.( will at least contain one element). So we will keep a Max variable and keep updating its value when we create the table values.

Here is the solution:

    2. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

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

Analyze: It is a classic example that we could use Dynamic programming to solve it easily and we will use a 2-D table for this problem.

1. We define out table be DP[i][j] be a boolean value = weather S.substring(i, j+1) is a valid palindromic substring.

2. DP[i][j] is true only when  S.charAt(i)==S.charAt(j)     &&    ( DP[i+1][j-1]  ||  (j-i)<3 )

3. Like the previous question, we will keep a max variable while we fill the table.

Here is a solution based on those steps:

Did you impress by the fact that we just used few lines of code to solve this question ?

One more thing to notice:

The loop sequence i-- , j ++ make sure that the previous value we are looking for dp[i+1][j-1] already finished !

     3. Unique BST

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

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

Analyze:

1.  We define our table be DP[i] = how many unique BST we can have that stores values 1... i.

2. Both DP[0] and DP[1] = 1, because we can have a null tree and a tree have a single node.

3. To figure out the recurrence relation is the key to this problem:

  Let H( i , n ) be how many unique BST we can create that stores 1...n values and have i as the head node.

 We know that DP[n] = H(1, n) + H( 2, n) + ... + H(n , n ).  ----------- ( 1 )

 Then Next problem becomes how to figure out H( i, n ).

-->  H( i , n) = DP[i -1 ] * DP[ n-i ]      -------------- ( 2 )

For example:  H( 3, 5 ) = DP[ 2 ] * DP[ 2 ]. ( We have two subtrees that have size 2 ).

Observe that relationship, we combine ( 1 ) and ( 2 ) get:

DP[n] = DP[0]*DP[n-1] + DP[1]*DP[n-2] + ... + DP[n-1]*DP[0]   

Which is our final recurrence relation?

4. The result will be found in DP[n].

Note  that after we realize there is a relationship between the current problem and  results of  previous solved problems, which are all stored in the table, then DP is the best method to solve this question.

Hope you will like Dynamic Programming as me :-)

Happy Coding ^^

Ye Jiang