Dynamic Programming

1. For each of the following dynamic programming problems, what would you choose the subproblems to be?

(a) Find the longest monotone subsequence of a sequence.

(b) Find the edit distance between two strings.

(c) Find the longest common subsequence of two sequences.

(d) Find the shortest distance between vertices s and t in a weighted acyclic directed graph.

(e) The knapsack problem.

(f) Find the n^{th} Fibonacci number.