How to find the nth Fibonacci number using the dynamic programming approach?
We can start solving the Fibonacci problem from bottom-up calculating partial solutions
We know the answer for the 0th and the 1st number of the Fibonacci sequence
And we know the formula to calculate each of the next numbers (Fi= Fi-1+ Fi-2)
Compare Fibonacci Solutions
Recurrent solution
Complexity: ~O(φn) = O(1.618n)
DP or memoization solution
Complexity: ~O(n)
Dynamic programming solutions is way faster than the recurrent solution
If we want to find the 36th Fibonacci number:
Dynamic programming solution takes ~36 steps
Recurrent solution takes ~48 315 633 steps
Subset Sum Problems
Given a set of integers, is there a non-empty subset whose sum is zero?
Given a set of integers and an integer S, does any non-empty subset sum to S?
Given a set of integers, find all possible sums
Can you equally separate the value of coins?
Subset Sum Problem Algorithm
Solving the subset sum problem:
numbers = {3,5,-1,4,2}, sum = 6
start with possible = {0}
Step 1: obtain all possible sums of {3}
possible = {0} ∪ {0+3} = {0,3}
Step 2: obtain all possible sums of {3,5}
possible = {0,3} ∪ {0+5,3+5} = {0,3,5,8}
Step 3: obtain all possible sums of {3,5,-1}
possible = {0,3,5,8} ∪ {0-1,3-1,5-1,8-1} = {-1,0,2,3,4,5,7,8}
…
Subset Sum Problem - Recursive
boolIsSubsetSumRecursive(int[] set, int n, int sum)
{
// Base Casesif (sum == 0)
returntrue;
if (n == 0 && sum != 0)
returnfalse;
// If last element is greater than sum, then ignore itif (set[n - 1] > sum)
{
return IsSubsetSumRecursive(set, n - 1, sum);
}
/* check if sum can be obtained by any of the following
(a) including the last element
(b) excluding the last element */return IsSubsetSumRecursive(set, n - 1, sum)
|| IsSubsetSumRecursive(set, n - 1, sum - set[n - 1]);
}
Subset Sum Problem - DP
boolIsSubsetSum(int[] set, int sum)
{
constint NotSet = -1;
var sumOfAll = set.Sum();
var last = newint[sumOfAll + 1];
var currentSum = 0;
for (var i = 1; i < sumOfAll; i++) last[i] = NotSet;
for (var i = 0; i < set.Length; i++)
{
for (var j = currentSum; j + 1 > 0; j--)
{
if (last[j] != NotSet &&
last[j + set[i]] == NotSet)
{
last[j + set[i]] = i;
}
}
currentSum += set[i];
}
return last[sum] != NotSet;
}
Longest Increasing Subsequence
Find a subsequence of a given sequence in which the subsequence elements are in increasing order, and in which the subsequence is as long as possible
This subsequence is not necessarily contiguous nor unique
The longest increasing subsequence problem is solvable in time O(n*log(n)) [more info]
We will review one simple DP algorithm with complexity O(n*n)
Example: 1, 8, 2, 7, 3, 4, 1, 6
LIS – Dynamic Programming
L[0] = 1; P[0] = NoPrevious;
for (int i = 1; i < S.Length; i++)
{
L[i] = 1;
P[i] = NoPrevious;
for (int j = i - 1; j >= 0; j--)
{
if (L[j] + 1 > L[i] && S[j] < S[i])
{
L[i] = L[j] + 1;
P[i] = j;
}
}
if (L[i] > maxLength)
{
bestIndex = i;
maxLength = L[i];
}
}
LIS – Restore the Sequence
voidPrintLongestIncreasingSubsequence(int[] sequence, int[] predecessor, int maxIndex)
{
var lis = new List<int>();
while (maxIndex != NoPrevious)
{
lis.Add(sequence[maxIndex]);
maxIndex = predecessor[maxIndex];
}
lis.Reverse();
Console.WriteLine("subsequence = "
+ string.Join(", ", lis));
}
Longest Common Subsequence
Given two sequences x[1..m] and y[1..n], find their longest common subsequence (LCS)
For example if we have x="ABCBDAB" and y="BDCABA" their longest common subsequence will be "BCBA"
LCS – Recursive Approach
S1 = GCCCTAGCG, S2 = GCGCAATG
Let C1 = the right-most character of S1
Let C2 = the right-most character of S2
Let S1' = S1 with C1 “chopped-off”
Let S2' = S2 with C2 “chopped-off”
There are three recursive subproblems:
L1 = LCS(S1',S2)
L2 = LCS(S1,S2')
L3 = LCS(S1',S2')
The solution to the original problem is whichever of these is the longest:
L1
L2
If C1 is not equal to C2, then L3
If C1 equals C2, then L3 appended with C1
This recursive solution requires multiple computations of the same sub-problems
This recursive solution can be replaced with DP
Initial LCS table
To compute the LCS efficiently using dynamic programming we start by constructing a table in which we build up partial results
We’ll fill up the table from top to bottom, and from left to right
Each cell = the length of an LCS of the two string prefixes up to that row and column
Each cell will contain a solution to a sub-problem of theoriginal problem
S1 = GCCCTAGCG
S2 = GCGCAATG
LCS table – base cases filled in
Each empty string has nothing in common with any other string, therefor the 0-length strings will have values 0 in the LCS table
for (i = 0; i <= n; i++)
{
c[i, 0] = 0;
}
for (i = 0; i <= m; i++)
{
c[0, i] = 0;
}
LCS – Dynamic Programming
int[,] LCS(string firstString, string secondString)
{
var m = firstString.Length;
var n = secondString.Length;
var c = newint[m + 1, n + 1];
for (var i = 1; i <= m; i++)
{
for (var j = 1; j <= n; j++)
{
if (firstString[i - 1] == secondString[j - 1])
c[i, j] = c[i - 1, j - 1] + 1;
else
c[i, j] = Math.Max(c[i, j - 1], c[i - 1, j]);
}
}
return c; // Answer in c[m, n]
}
LCS – Reconstruct the Answer
voidPrintLCS(int i, int j, int[,] c)
{
if (i == 0 || j == 0) return;
if (FirstString[i - 1] == SecondString[j - 1])
{
PrintLCS(i - 1, j - 1, c);
Console.Write(SecondString[j - 1]);
}
elseif (c[i, j] == c[i - 1, j])
{
PrintLCS(i - 1, j, c);
}
else
{
PrintLCS(i, j - 1, c);
}
}
Demo: Moving Problem
In many DP problems there is a moving object with some restrictions
For example: In how many ways you can reach from top-left corner of a grid to the bottom-right?
You can move only right and down
Some cells are unreachable
DP Applications
Matematical, finance and economic optimizations
Optimal consumption and saving
The core idea of DP is to avoid repeated work by remembering partial results. This is a very common technique whenever performance problems arise
Bioinformatics
sequence alignment, protein folding, RNA structure prediction and protein-DNA binding
Control theory, information theory
Operations research, decision making
Computer science:
Theory, Graphics, AI
Markov chains
Spelling correction
Some Famous DP Algorithms
Integer Knapsack Problem
Unix diff for comparing two files
Dijkstra’s algorithm for the shortest path problem
Bellman–Ford algorithm shortest distance in a graph
Floyd’s All-Pairs shortest path algorithm
Cocke-Kasami-Younger for parsing context free grammars
Methods for solving the travelling salesman problem
Some methods for solving interval scheduling problems
