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

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

Having Fun with BST #2

                 Binary Search Tree Problems (#2)  

After we covered how to traverse a BST, we will go head to try some different problems about BST now ! 

          1. Valid Binary Search Tree 

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

    2
   / \
  1   3

Binary tree [2,1,3], return true.

Example 2:

    1
   / \
  2   3 

Binary tree [1,2,3], return false. 

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

Analyze: What is the first solution comes to your mind ? 

Solution 1: If you still remember the 5 basic ways we traverse a BST, you will find a straightforward way to do it --> 1. Do a inOrder traversal. 2. See if you get a ascending order sequence. 

The code will be very similar to what we did on a inOrder traversal: 

Solution 2: Here is a more elegant approach: 

This approach is based on the definition of BST that the values in left subtree will smaller than current node and the values in right subtree will greater than current node. We narrow the scope every time call the recursive function isValid. 

Can you come up solution 3 ? 

     2. Binary Search Tree Iterator 

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

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

QUIZE: Do you know which data structure we will use in this problem ?  ( Hint: Consider the relationship between this problem and  In Order traversal) 

Analyze: The idea is very similar to the iterative way to do a in order traversal, because a iterator actually will return the values in the BST in ascending order. 

So we keep a stack and make sure the smallest value is in the top of this stack. 

       3. In-order Successor in BST 

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

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

Analyze: In order successor should be the next value that bigger than current node's value.  There are 2 cases we need to consider : 1: this node has right child. 2. this node do not have a right child. 

For the first case, we simply find the Min value in its right sub-tree. 

For the second case, we need to keep going upwards to search its parents, until we find the first parents that is bigger than its value ( or there is no successor exist) 

      4. Kth Smallest Element in a BST 

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

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

Analyze:  The most elegant way to solve this question will utilize the property of BST. We actually covered this question in the we want Kth element , but it is good for us to practice again :-) 

There are so many questions about BST that I can't cover all of them, but recursive method, the property of BST are two keys to remember when you solving them. Hope this two article give you a pretty good start point to discover more about BST. 

Happy Coding^^ 

Ye Jiang 

Having Fun with BST #1

                   Binary Search Tree Problems(#1) 

A Binary Search Tree (BST) is a tree data structure that follows two properties

 1. Left sub-tree of a node has value less or equal to this  node's value.

 2.Right sub-tree of a node has value greater than or equal to this node's value.

With this two properties, BST is a powerful tool to store and retrieve data.  Here is some operations that support by BST and the time complexities.

  --   Search :  O(log N )

  --  Insert     :  O(log N )

  --  Delete    :  O(log N )

In order to search a target in BST, obviously, we need to traverse a BST.  Let's, then, see how we can traverse a BST.

Here are 3 general ways to traverse a BST:  

Pre - Order Traversal

In - Order Traversal

Post - Order Traversal  

We will walk through how to do them one by one, Besides, I would like to cover 2 other interesting way to do traverse.

Level - Order Traversal

ZigZag - Order Traversal

Ready ? Let's Roll !

Example Tree :

   

1. Pre - Order Traversal 

Basic idea of Pre - Order Traversal in pseudo code will be :
1. Visit the Current node.
2. Visit its Left Child
3. Visit  its Right Child

The result using this method to traverse the example tree above will be :
8 --> 3 --> 1 --> 6 --> 4 --> 7 --> 10 --> 14 --> 13.

Here is the recursive code for Pre-Order Traversal:


Here is the iterative code:




Notice that the sequence of stack push right child and then left child can not be change. 

 2. In-Order Traversal 

 This way in pseudo code will be:

1. Visit its Left Child.
2. Visit  the Current Node.
3. Visit  its Right Child

The result using this method to traverse the example tree above will be :
1 --> 3 --> 4 --> 6 --> 7 --> 8 --> 10 --> 13 --> 14

Notice that if a BST is valid the result of in-Order traversal is always sorted in increasing order. 

Recursive code:


Iterative code become Interesting :

3 . Post- Order Traversal

The pseudo code for post order will be:

1.Visit its Left Child
2.Visit its Right Child
3.Visit the Current Node
The result using this method to traverse the example tree above will be :
1 --> 4 --> 7 --> 6 --> 3 --> 13 --> 14 --> 10 --> 8

Recursive code will be:



Iterative way to do post-Order become easy when you have two stacks: 

4. Level-Order Traversal 

Yes! Just like the name. We gonna traverse our tree level by level. So here is the result sequence when we use level-Order traversal:
8 --> 3 --> 10 --> 1 --> 6 --> 14 --> 4 --> 7 --> 13

Here is a little quiz: What data structure you think gonna help us traverse tree this time ?

So, Previous we used stack a lot, but this time we gonna use a Queue, which actually make sense since it is like a BFS in a BST.

Here is how we gonna use a queue to do level-order traversal:

5. ZigZag - Order Traversal

Also like the name we will traverse the tree levelly by in ZigZag order !
Actually here is a question about this in LeetCode:

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Here is a solution using two stacks:



I think the code is very straightforward  and pretty much self-explained everything we want to do here.

Hope you had your favorite way to traverse a BST now :-)

Happy Coding^^
Ye Jiang