1.2 多维数组
多维数组这种数据结构，运用特别频繁。二维数组用于线性代数，三维数组用于Floyd-Warshall算法。当然还有别的用途。
这里按照套路，以一个需求开始。我选择了面试经常问的，经典的LCS问题，LCS是Longest Common Subsequence的缩写，也就是求最长共同子字符串的长度。
举个例子，两个字符串分别为：
ABCBDAB
BDCABC
最长的子字符串是BCAB（例子中加粗的部分）或BDAB。
对于这个问题，我们需要认真分析需求，需求是求子字符串，可以是不连续的，比如上例中的BCAB，在第一个字符串中就夹杂了BD两个字符。依旧使用高中数学的分类归纳法：
第一种场景，两个字符串尾部字母相同：
如ABCBDAB与BDCAB
那么LCS就是ABCBDA与BDCA的LCS加上字母B。
第二种场景，两个字符串尾部字母不同：
但是这种场景又分两种子场景：
如ABCBDAB和BDCABC，这个场景那么LCS可能等于ABCBDAB和BDCAB的LCS（结果为BCAB），也可能等于ABCBDA和BDCABC的LCS（结果为ABC），两种我们肯定取更长的，所以取BCAB。定义两个字符串为X和Y。这种场景的LCS，需要计算X去掉尾部,Y不变的LCS和X不变，Y去掉尾部的LCS，然后取两个LCS之中的最长者。
所以可以定义一个二元函数d(x,y)，x代表字符串X的索引，y代表字符串Y的索引。d(x,y)就是X从索引0到索引x的子串和Y从索引0到索引y的子串的LCS。
所以这个和二叉树数量的问题一样，也是递归问题。那么最合适的数据结构是什么？肯定是二维数组啊。二维数组有两个索引，一个索引表示X的子字符串长度，一个索引用来表示Y的子字符串长度。数组内存储两个子字符串的LCS。X去掉尾部就是行索引-1，Y去掉尾部就是列索引-1。
用公式描述就是
上述字符串ABCBDAB与BDCABC产生的LCS长度二维数组是这样的：
理清楚了需求，代码就比较容易写了，以下是python代码：
def lcs_len(x, y): len_x = len(x) len_y = len(y) array = [[0 for _ in range(len_y + 1)] for _ in range(len_x + 1)] for i in range(1, len_x + 1): for j in range(1, len_y + 1): if x[i - 1] == y[j - 1]: array[i][j] = array[i - 1][j - 1] + 1 else: a = array[i - 1][j] b = array[i][j - 1] array[i][j] = a if a > b else b for e in array: print(e) return array[len_x][len_y]因为python并没有真正的数组，所以这里补上java代码：
public static int lcsLength(String x, String y) { int lenX = x.length(); int lenY = y.length(); int[][] array = new int[lenX + 1][lenY + 1]; for (int i = 0; i <= lenX; i++) { array[i][0] = 0; } for (int i = 0; i <= lenY; i++) { array[0][i] = 0; } for (int i = 1; i <= lenX; i++) { for (int j = 1; j b ? a : b; } } } return array[lenX][lenY];}