[Algorithms][DP] Thinking in DP - 0

We will discuss a few problems and how to solve them using binary programming in this post.

0. n th fibonacci number:
Recurrence relation:
f(n) = f(n-1) + f(n-2)

Base case:
f(0) = 0
f(1) = 1

Complexity:
Number of sub problems = n,
Time to solve one sub problem = 0(1)
Total order = O(n)

Naive complexity: O(2 ^ n), as each recursive call will do full computation instead of using previous computed value.

1. n choose k (binomial coefficient)
Recurrence relationship:
f(n, k) = f(n-1, k-1) + f(n-1, k)
Explanation: 
From ABCD how many combination you can form taking only 3 of them?
Total combinations: ABD, ACD, BCD, ABC.

Ignore D first, compute how many 2 element item can be formed from ABC
AB, AC, BC. We can just add D at last position and we will get
ABD, ACD, BCD, this gives f(n-1, k-1).
Now, lets see how many 3 length String we can form from ABC (still ignoring D). Just 1, ABC.
this gives, f(n-1, k) 

Base case:
f(n, 0) = 1
f(n, n) = 1

Complexity:
From the equations, we will need to fill up a 2D array. Intuitively, it tells the order would be O(n ^ 2).
Number of subproblems: O(n ^ 2) [for each value of i of n, we will have to iterate all the values from 0 to i]
Time to solve one sub-problem: O(1)
Runtime = O(n^2)
Naive Complexity: O(2 ^ n)

2. Longest Common Sub-sequence:
Problem: Find the longest common sub-sequence of two strings.
Recurrence:
f(i, j) = if (a[i] == b[j])
                f(i - 1, j - 1) + 1
             else
                max(f(i, j - 1), f(i - 1, j))

Explanation: a = ABABDCD, b = AXBYCZ are two strings. Note that, the longest common sub-sequence is ABC. f(i, j) means find the length of the longest common sub-sequence in a[0..i] and b[0..j].

Base case: f(n, 0) = f(0, n) = 0
Complexity: O(n ^ 2). Same reasoning as above.
Naive Complexity: O(2 ^ n) if all the f is computed separately.
Backtracking can be applied here as well.
Generate all possible subsets of characters in string a. (2 ^ n)
Generate all possible subsets of characters in string b. (2 ^ n)
Find the sub-string of maximum length of the 2 subsets.

3. Maximum sum contiguous sub array
Problem: Given a 1-D array, find the contiguous sub array with the maximum sum.
Recurrence: At first compute all the sum of starting from i ending at j.
f(i, j) = f(i, j - 1) + f(j, j)
find the cell with the maximum value in it.

Complexity: O(n ^ 2)

4. Maximum size square sub array with all 1s:
Problem: Given a 2D array A holding 0 or 1 in cells, find the maximum sub 2D array that is square and that has all element 1.
Recurrence: Construct an auxiliary 2D array S such that
S(i, j) = min(S(i - 1, j), S(i, j - 1), S(i - 1, j - 1)) + 1 if A(i, j) = 1
S(i, j) = 0 if A(i, j)  = 0
Base case, S(0, j) = A(0, j), S(i, 0) = A(i, 0)
S(i, j) essentially holds the size of the maximum square sub array all holding 1 whose bottom right corner is A(i, j).

After constructing, S, find the S(i, j) with maximum value.

Complexity: O(n ^ 2) as we are constructing a 2D array.