辅导LCS留学生、辅导R编程语言、讲解subsequence、辅导R设计
调试C/C++编程|讲解SPSS
Problem 18. (Difficulty 2) Recall that in the dynamic programming algorithm for finding
the length of a longest common subsequence between two strings S and T, we define
the subproblem LCS(i, j) to be the length of a longest common subsequence between the
substrings S[1..i] and T[1..j], and we have the recurrence
LCS(i, j) = (
max{LCS(i 1, j), LCS(i, j 1)} if S[i] 6= T[j]
LCS(i 1, j 1) + 1 if S[i] = T[j].
Suppose S = ALBAI and T = BILAAC. Fill out the matrix that contains the value for each
subproblem LCS(i, j).
For example, if S = ADH and T = JALH, then we have the following matrix:ij
0 1 2 3 4
0 0 0 0 0 0
1 0 0 1 1 1
2 0 0 1 1 1
3 0 0 1 1 2
Problem 19. (Difficulty 3) There are n trading posts numbered 1 to n as you travel downstream.
At any trading post i you can rent a canoe to be returned at any of the downstream
trading post j > i. You are given a cost array R, where R(i, j) is the cost of renting a canoe
from post i to j for 1 ≤ i < j ≤ n. You cannot go upstream. Design a dynamic programming
algorithm to compute the cheapest cost to get from post 1 to n. Make your algorithm as
fast as you can.
For example, suppose n = 4 and the cost matrix R(i, j) is ij
1 2 3 4
1 - 2 3 7
2 - - 2 4
3 - - - 2
4 - - - -
The cheapest way to reach post 4 from 1 is by renting a canoe from 1 to 3, and then from 3
to 4 for a total cost of 3 + 2 = 5.
Problem 20. (Difficulty 3) Describe an O(n2)-time algorithm to compute a longest increasing
subsequence of a sequence of n numbers. Note you have to output the entire sequence,
not just its length. Also recall that the elements of a subsequence need not be consecutive.
Problem 21. Given an n × n matrix A(i, j) of integers, determine in O(n2) time the maximum
value A(c, d) A(a, b) over all choices of indexes such that both c > a and d> b.