Suppose you want to dial a telephone number consisting of n

digits on a standard 12-button telephone keypad, using the index fingers of both hands. Assuming both fingers start over the 1 button, devise an O(n)

time algorithm using dynamic programming (In particular, give the

recursive formulation) which determines which finger to use for each of the

n digits so as to minimize the sum of the total distance traveled by both fingers. Assume that the distance between two buttons I and j is given by the function dist(i,j). You should first give the recursive formulation, clearly

explaining what the subproblems are. Then devise two efficient algorithms

that implements your recursive formulation a recursive algorithm (using top-down, lookup strategy) and an iterative (DP, bottom-up strategy).

Analyze the running time of your algorithms.