1.2 多维数组（markdown版本）

多维数组这种数据结构，运用特别频繁。二维数组用于线性代数，三维数组用于Floyd-Warshall算法。当然还有别的用途。
这里按照套路，以一个需求开始。我选择了面试经常问的，经典的LCS问题，LCS是Longest Common Subsequence的缩写，也就是求最长共同子字符串的长度。
举个例子，两个字符串分别为：
ABCBDAB
BDCABC
最长的子字符串是BCAB（例子中加粗的部分）或BDAB。
对于这个问题，我们需要认真分析需求，需求是求子字符串，可以是不连续的，比如上例中的BCAB，在第一个字符串中就夹杂了BD两个字符。依旧使用高中数学的分类归纳法：

1. 第一种场景，两个字符串尾部字母相同：
   如ABCBDAB与BDCAB
   那么LCS就是ABCBDA与BDCA的LCS加上字母B。
2. 第二种场景，两个字符串尾部字母不同：
   但是这种场景又分两种子场景：

• 如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。
用公式描述就是：
d(x,y)={d(x−1,y−1)+1X[x]=Y[y]max(d(x−1,y),d(x,y−1))X[x]!=Y[y] d(x,y)=\begin{cases} d(x-1,y-1)+1 & X[x]=Y[y]\\ max(d(x-1,y),d(x,y-1)) & X[x]!=Y[y]\\ \end{cases}d(x,y)={d(x−1,y−1)+1max(d(x−1,y),d(x,y−1))​X[x]=Y[y]X[x]!=Y[y]​
上述字符串ABCBDAB与BDCABC产生的LCS长度二维数组是这样的：

代码实现

​
理清楚了需求，代码就比较容易写了，以下是python代码：

deflcs_len(x,y):len_x=len(x)len_y=len(y)array=[[0for_inrange(len_y+1)]for_inrange(len_x+1)]foriinrange(1,len_x+1):forjinrange(1,len_y+1):ifx[i-1]==y[j-1]:array[i][j]=array[i-1][j-1]+1else:a=array[i-1][j]b=array[i][j-1]array[i][j]=aifa>belsebforeinarray:print(e)returnarray[len_x][len_y]

因为python并没有真正的数组，所以这里补上java代码：

publicstaticintlcsLength(Stringx,Stringy){intlenX=x.length();intlenY=y.length();int[][]array=newint[lenX+1][lenY+1];for(inti=0;i<=lenX;i++){array[i][0]=0;}for(inti=0;i<=lenY;i++){array[0][i]=0;}for(inti=1;i<=lenX;i++){for(intj=1;j<=lenY;j++){if(x.charAt(i-1)==y.charAt(j-1)){array[i][j]=array[i-1][j-1]+1;}else{inta=array[i-1][j];intb=array[i][j-1];array[i][j]=a>b?a:b;}}}returnarray[lenX][lenY];}