All Pairs Shortest Path
Let be the shortest path in (a weighted graph with non-negative edge weights) from to that uses only vertices . Then we can express as . This is because either the shortest path from to using does not use the vertex at all (thus the term ) or it uses the vertex in which case it only visits once (since it is a shortest path and the edge weights are non-negative) and hence we get the term . Thus one can fill the table in a bottom up manner giving a running time of .
Longest Increasing Subsequence
Given a sequence of integers find the length of the longest increasing sub-sequence. To apply the dynamic programming paradigm we need to find a table that can be filled efficiently and that gives us the answer. Let denote the longest subsequence that ends with . We can express as
This gives us an algorithm to solve this problem.
We are given two words and and we wish to compute the edit distance between them. The edit distance is defined as the minimum number of insert, delete and replace operations that we need to do to transform the first string into the second. Insert operation allows us to insert a character, delete allows us to delete a character and replace allows us to replace a character with another character.
Let represent the edit distance between and . Then we may write as
where if and otherwise. Filling up the table either row wise or column wise gives us an algorithm with running time .