[AlgorithmS][DP] Thinking in DP -1

5. Longest Increasing sub sequence:
Problem: Given a sequence, find the longest increasing sub sequence. LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.
Recurrence: Given an Input array, I. Build an auxiliary array of same size as I, A such that.
A(i) = max(A(j)) + 1, if an entry is found in I, such that i > j and j >= 0 and I(i) > I(j)
else A(i) = 1
Base case: A(0) = 0
Runtime:
Number of sub-problems = O(n).
Time to solve a sub-problem = O(n), as to build A(i) we need to traverse A(0) through A(i-1).
Total runtime = O(n ^ 2).

6. Given available coin values, {a, b, c} what is the minimum number of coins required to give change for n Cents.
Recurrence: f(n) = min(f(n-a) + f(n-b) + f(n-c)) + 1
base case:
f(0) = 0
f(a) = 1
f(b) = 1
f(c) = 1
f(-coinval) = + infinity
Runtime: Number of sub-problems = O(n), time to solve a sub-problem = O(m), here is m is the size of coin types.
Total runtime = O(m * n)

7. Edit distance
Problem: Given two strings a and b, find minimum number of elementary character operations (insert, delete, replace) to convert a to b.
Example:
f(UTEP, KTEP) = 1 (replace U by K)
f(RATS, BAT) = 2 (replace R by B, delete S)
Recurrence:
f(i, j) = f(i - 1, j - 1) if a[i] == b[j] 
f(i, j) = min(f(i, j - 1), f(i - 1, j), f(i - 1, j - 1)) + 1 if a[i] != b[j]
base case:
f(0, 0) = 0
f(i, 0) = i
f(0, j) = j
Explanation: f(i, j) is the edit distance of string a[0...i] and b[0...j]. Let, a = FIAS, b = FITA.
Here, we want to compute f(3, 3). Here, a[3] != b[3] so we need to insert, delete or replace.
In string a, if we choose to,
insert   A then we need to convert          FIASA -> FITA   >> f(i, j - 1)
delete   S then we need to convert          FIA -> FITA        >> f(i - 1, j)
replace S by A then we need to convert FIAA -> FITA     >> f(i -1, j - 1)
Runtime: Number of subproblems = O(n ^ 2), we are constructing a 2D array.
Time to solve a sub problem = O(1)
Total order = O(n ^ 2)
Naive order: f(i, j) ~ 3f(i-1, j-1) = O(3 ^ n)
                                                                                                    
8. Cutting Rod
Problem: A rod with n length is given. Value of all rod length 1..n is given. Find the maximum profit can be obtained by cutting the rod in optimal way.
Recurrence:
f(n) = max( max(f(n-i) + f(i)) for n > i  > 0, val[n])
base case:
f(0) = 0
Explanation: n = 4. We need to know which one gives the most profit, the max of val[4], f(1) + f(3), f(2) + f(2).
Runtime:
Number of sub-problems = O(n).
Time to solve a sub-problem = O(n), as we need to traverse all the values f(0) to f(n-1).
Total runtime = O(n ^ 2)

9. Subset Sum
Problem: Given a set of numbers, S and a number n, find if any subset of S sums up to n.
Recurrence:
f(i, n) = f(i - 1, n) | f(i - 1, n - S[i])
base case:
f(0, n) = false where n > 0
f(i, 0) = true where i >= 0
Explanation: f(i, n) represents if a subset from S[0...i] sums to n.
f(i - 1, n) is if a subset of S[0...i-1] sums to n.
f(i - 1, n - S[i]) is if a subset of S[0...i-1] sums to n - S[i] if so then including S[i] would sum to n.
Runtime:
Number of sub-problems = O(|S| * n)
Time to solve one sub-problem = O(1)
Total runtime = O(|S| * n)
The order depends on the value n holds, this scenario is known as Pseudo-Polynomial.