矩形面积

我们在小学就学过矩形的面积等于长乘以宽。

但活了几十年，你有没有想过：矩形面积为啥等于长乘以宽？

或者说先人们为何将矩形的面积定义为长乘以宽？

（继续之前，请先忘掉矩形面积等于长乘以宽这个“简单”的知识）。

设想自己是个好奇心极强的农夫，某天闲来无事，端着一杯茶盯着自家一块地，就像下面这形状：

我们突然想搞清楚这块地有多大。于是用尺子量了量：

这块土地大小是长 100 宽 50。

但我们那该死的好奇心对这个结果并不满意：它想知道这么大的矩形所围出来的区域（阴影部分）到底是多大——它想用一个数字来表达这个区域。

在搞清楚答案之前，得先给它起个名字。

叫什么都行，最好直观，比如区域、面积——不妨就叫面积吧。

另外我们想求解的是通用矩形的面积（而不是长 100 宽 50 的”这个“矩形），所以我们决定用一些符号来表示矩形的长和宽。不妨用 l（或者别的什么符号都行）代表长，用 w 代表宽。

l 和 w 的含义是任意长宽的矩形。

现在问题变成：求长 l 宽 w 的矩形的面积是多少？

注意我们如何将问题符号化。

答案是：不知道！

到目前为止，我们脑袋里的数学知识只有数字、加、减和乘——面对这个陌生的”面积“，我们一筹莫展。

人类有个天生的”优点“：善于自欺欺人。

我们不知道矩形面积是多少对不对？可以假装知道啊！

就像我们将矩形的长和宽符号化一样，我们也可以给面积一个符号。

给什么符号无所谓，X、Y、面、# 都行——不妨管它叫 S 吧（虽然后人总是从历史的角度来考证符号的含义，但实际上给它什么符号真的无所谓）。

现在我们好像多了一点知识：知道了长 l 宽 w 的矩形的面积是 S。

但实际上我们又什么都不知道——其实不然，我们凭经验感觉这个 S 和 l、w 有关系（有什么关系还不清楚）。

为了表示这个”重大“的发现（S、l、w 之间存在某种关系），我们给出如下缩写：S(l,w)。

（用其它任何缩写都行，比如 S[l,w]、l,w -> S 等等，我们之所以用 S(l,w) 纯属个人偏好。）

S(l,w) 和 S 这两种表达其实是一个意思，都是表示矩形的面积，只不过前者多了进一步的含义：矩形的面积和长 l、宽 w 多少存在某种关系。

接下来我们自然就会想：它们到底存在什么关系呢？

注意我们如何将求解问题转变成求解关系。

我们低头思考了半天不得其解。

就在我们快放弃的时候，我们的眼角余光瞟向那一亩三分地，我们想：既然它们存在关系，那我就试着改变长和宽，看看面积会发生什么变化？

变量变量，既然它是可变的，就让它变化吧——只能在变化中发现关系。

首先，我们把长 l 加倍：

我们发现，长加倍后，面积也明显加倍了，于是得到如下等式：

S(2l,w) = 2S(l,w)

我相信你第一次感受到了符号化的力量！

有点意思！

接下来将长保持不变，宽加倍试试：

面积同样加倍了：

S(l,2w) = 2S(l,w)

我们觉得看到希望了！

于是我们拿起树枝在地上画起来——我们发现，无论长、宽增加（或减少）多少倍，面积都跟着增加（或减少）一样的倍数。于是我们写下了如下式子：

S(#l,w) = #S(l,w)

S(l,#w) = #S(l,w)

# 表示任意数。上面的式子是说：我们可以将矩形的长拆分成两个任意数（#、l）的乘积，然后将其中一个数从括号里面拿出来。对于宽也是如此。

接下来就要发挥人类的推理能力了。

也是考验人智商的时候。

S(l,w) 可以写成 S(l*1,w)。按照上面的式子，我们可以将 l 从括号里面拿出来得到：

S(l,w) = S(l*1,w) = l*S(1,w)

我们再对 w 做同样的处理，得到：

S(l,w) = S(l*1,w) = l*S(1,w) = l*S(1,w*1) = l*w*S(1,1)

也就是说：S(l,w) = l*w*S(1,1)。

至此我们得到结论：长 l 宽 w 的矩形的面积是 长 1 宽 1 的矩形的面积的 l*w 倍。

我们并没有得到一个绝对数，而是得到了一个相对于 长 1 宽 1 的长（正）方形的面积的倍数。

因为这个长 1 宽 1 的矩形面积总是固定的，所以我们并不需要关心它的面积绝对值到底是多少，我们可以把它人为地定义为 1，那么长 l 宽 w 的矩形的面积就是 l*w。

这个思想很重要：我们在现实世界中理所当然地认为是绝对值的（比如这里的面积），其实本质上是相对值。

比如 3 米到底是多长？它取决于 1 米有多长。

1 分钟有多久？它取决于 1 秒有多久。

这些作为度量参照的，我们称之为单位。

最底层的单位是人为定义的，而且在人类的不同历史时期可能有不同的定义。比如中国古代的 1 斤跟现代的 1 斤在重量上并不相等，但它并不妨碍两个时代人的日常使用。

发生了什么？

在一般人看来，数学是人类最严谨的学科，就好像是神灵赐予人类的先验礼物。

数学是严谨不假，但数学的基础并不是先验的，而是源自人类生活的经验。

虽然数学中充斥着大量的公理、证明啥的，但数学最底层却是一些”简单“的公设（公理。比如平面几何学中的五大公设）。小学老师告诉我们：所谓公理，是不需要证明的（不证自明）。这个所谓的”不证自明“，说白了就是凭经验。

不但数学中最基本的公理凭经验，数学中的很多求证过程也是凭经验——虽然听起来不可思议。

我们回头看看矩形面积的推导过程：

一开始我们只是好奇心作怪，想知道如何用数来表示这么一块矩形区域（定义问题）。

我们发现自己不知道怎么求解它，没办法只能给它个代号（符号化）。

另外我们发现矩形有两个属性：长和宽（参数化）。

经验告诉我们，矩形面积跟矩形的长和宽存在某种关系（关联）。

于是我们根据经验试图去寻找它们之间到底存在哪些关系（找规律）。

经过穷举，我们得到了几个很有意思的等式。

再经过一番思考和观察，我们发现这几个等式可以泛化成一般等式（就是里面的具体数值可以变量化）。（关系泛化）

面对一般化的等式，我们利用已有知识（如 w = w * 1，即一个数乘以 1 等于它自身，这是根据乘法的定义得出的结论），最终推导出我们想要的东西（基于既有知识的推理）

在整个过程中，经验、观察、实验、符号化起到非常重要的作用。

关程序员何事？

这里涉及到我们如何思考和解决问题。

当我们面临一个陌生的（而且看起来很难的）问题时，本能反映是摸不着头脑。

然后就开始抓瞎。

我们要做的是，在抓瞎之前冷静一下，看看远方，做几次深呼吸，再多想几次问题本身。

不要在还没搞清楚问题是什么之前就开始解决问题。

我们举个字符串编辑距离的例子。

问题：给定两个字符串 str1 和 str2，求 str1 至少需要经过多少次操作才能变成 str2。

你第一次遇到这个问题是什么感受呢？反正我是一脸懵逼，狗咬刺猬，无处下牙。

然后的感觉是：这个问题我好像没怎么弄明白？

所以要先分析问题本身。

什么叫”经过多少次操作“？

想要知道经过多少次操作，起码先要知道都有什么样的操作吧？

我们记得前面那位老农是面对着一亩三分地思考问题——而我们现在面对的是两个抽象的（符号）str1 和 str2。

所以接下来要将抽象的问题具象化。

我们不妨写两个具体的字符串：

str1 = "abcd"

str2 = "acdb"

现在变成了具体的问题：怎样通过最少的操作将字符串"abcd"变成"acdb"？

这个问题其实分两部分：

1. 怎样的操作？
2. 最少的操作？

一个字符串想变成另一个字符串，它总要一个字符一个字符地处理吧（你不可能连看都不看某个字符就能做出正确决定）。

所以”操作“这个概念就变成了”一个字符怎样变成另一个字符“的问题。

我们就看第一个字符：str1 中的 a 如何变成 str2 中的 a？

想都不用想，它俩相等，不用做任何操作——不做任何操作本身就是一种操作类型。

然后我们看看第二个字符：str1 中的 b 如何变成 str2 中的 c？

它俩不一样，所以必须做些行动才行。

一种方案是，将 b 替换成 c。

第二种方案是，将 b 删除掉，让其它的字符（可能是插入的新字符）来应对 c 这个字符。

第三种方案是，在 a 和 b 之间插入 c。

没有其他方案了。

至此我们搞明白了所谓”操作“到底是什么：啥也不做、替换、删除、插入，一共四种。

然后我们再把那个恐怖的修饰语”最少的“加上去——你会发现此时头又大了。

如果不限制”最少“，其实很好办，最无脑的做法就是先把 str1 中的字符全删掉，然后再一股脑把 str2 中的每个字符挨个插入即可，操作步数是 n + m（两个字符串长度之和）。

这个最无脑的解法虽然无用，但它揭示了该问题的最大操作步数是 n+m，所以如果你整出的解比它还大，那肯定不对了。

我们再回到上面的具体字符串：怎样通过最少的操作将字符串"abcd"变成"acdb"？

我们一个一个尝试。

其中一种方案是：第一个 a 保持不变，删掉第二个 b，最后在 d 后面插入 b，操作步数是 2。

然后我们又人肉尝试了其它方案，发现所有方案中最小的就是 2。

然而，问题好像并没有什么进展——我们仍然不知道如何求得最少步数（除了人肉）。

如果我们的思路一直停留在具体问题上，便不太可能得到问题的解。

人类区别于其他动物的地方在于，人类能够将具象的事物（现象）提升成抽象的符号，进而形成思维模型（这也正是数学的奥秘，现在你应该能够理解数学家为啥那么喜欢玩符号了）。

将问题具象化有助于我们深刻理解问题本身，现在是时候让思维从具象回到抽象层面了。

我们先对字符串本身做抽象化表述。

字符串就是字符序列，它的本质就是集合（外加了个限制：顺序相关，即里面的字符有特定顺序）。

所以问题变成：如何通过最少操作步数将长度为 n 的字符序列 \(\{x,y,z\cdots\}_n\) 转换成长度为 m 的字符序列 \(\{x^\prime,y^\prime,z^\prime\cdots\}_m\)？

答案是：不知道！

那位农夫在求不出面积的时候做了个惊人的举动：给它个符号！

我们也这么办。

我们假设 \(\{x,y,z\cdots\}_n\) -> \(\{x^\prime,y^\prime,z^\prime\cdots\}_m\) 的最小编辑距离是 N（管它怎么求的）。

跟农夫将 S 换成 S(l,w) 以体现面积和边长的关系一样，我们也将参数放进去：

N(str1, str2)

这个组合符号是说：它能算出字符串 str1转换为 str2 的最少操作步数（最小编辑距离）。

至于怎么算的，我们暂时不关心。

这玩意是不是像极了编程中的接口？

作为程序员，你可能觉得这个 N 太丑了，那我们换个”人性化“点的符号（名字）：shortestEditDist(str1, str2)。

然后——我们盯着这奇怪的符号思考了半天，一筹莫展！

符号本身并不能告诉我们更多，我们必须开动推理的马达去加工符号。

对于集合类型问题，我们常用的一种思维模式是：通过子集的解推出父集的解。

具体地，对于”串“类的问题，假如我们已经知道某个子串的解，看能否通过这个子串推出某个父串的解。

作这种解题假设的依据是：子串和父串具有相同的模式。

于是我们把那个“无知而又牛逼”的组合符号（也就是函数）稍作调整：

shortestEditDist(str1, str2, i, j)

多了两个参数 i 和 j。它是说：我知道子串 str1[0,i] -> str2[0,j] 的最小编辑距离 M（其中 0<=i<n, 0<=j<m）——别管我是怎么知道的。

如图：

我们想让问题稍微得到推进。

于是我们问自己：我们怎样得到 str1[0,i+1] -> str2[0,j+1] 的解？

根据我们之前对字符转换的分析可知有四种操作：

方案一：当 d 等于 \(d^\prime\) 时，不用做任何操作。

如图：

公式：shortestEditDist(str1, str2, i+1, j+1) = shortestEditDist(str1, str2, i, j)

否则：

方案二：先求出 str1[0,i] -> str2[0,j+1] 的解，然后删掉 d。

如图：

公式：shortestEditDist(str1, str2, i+1, j+1) = shortestEditDist(str1, str2, i, j+1) + 1

其中的 +1 表示删除 d 的操作。

方案三：先求出 str1[0,i+1] -> str2[0,j] 的解，然后在后面插入 \(d^\prime\)。

如图：

公式：shortestEditDist(str1, str2, i+1, j+1) = shortestEditDist(str1, str2, i+1, j) + 1

方案四：先求出 str1[0,i] -> str2[0,j] 的解，再将 d 替换成 \(d^\prime\)。

如图：

公式：shortestEditDist(str1, str2, i+1, j+1) = shortestEditDist(str1, str2, i, j) + 1

四种方案，用谁呢？不知道，只能全部求出来取结果最小的。

看了上面的推导，你是不是心里虚得不行？

用一堆“一无所知”的公式推来推去，自娱自乐？

不要不信邪，前面的面积公式不就是在“一无所知”的情况下自推自导搞出来的吗？

既然我们假设已经知道 shortestEditDist(str1, str2, i, j) ，而这里的 i、j 的范围又是 0<=i<n, 0<=j<m，那我们自然可以在有效范围内随便取值（也就是说取 i、i+1、j、j+1 都是合法的）。

注意：严格来说 i+1、j+1 会越界的，但我们暂时不考虑越界情况。

所以我们就可以将诸如 shortestEditDist(str1, str2, i+1, j) 放在等式右边作为“已知值”来求shortestEditDist(str1, str2, i+1, j+1)。

有同学可能会说：那我们也可以假设 shortestEditDist(str1, str2, i+1, j+1) 已知啊？

是的，你可以随便假设，但如果所有问题都“假设已知”了，那就真的自欺欺人了，对问题求解没有一点好处。

这种看似是文字游戏的逻辑伎俩，本质是在寻找关系。

是的，我们最看重的是关系，而不是某个式子的绝对解。所以我们可以在推理的时候，将某些东西设为已知，而将另一些东西进一步符号化（想想高中学习的所谓的“复合函数”，大学学的高阶求导——多半你是想不起来了）。

我们写一下代码：

// 我能算出子串 str1[0,i] 转换为 str2[0,j] 的最小编辑距离，其中 0 <= i < n，0 <= j < m
func shortestEditDist(str1, str2 string, i, j int) int {
	// 还没想好怎么实现...
}

// 求 str1 转成 str2 的最小编辑距离
func EditDistance(str1, str2 string) int {
	// 既然你做了那样的声明，我就这样用
	// 算不出来唯你是问！
	return shortestEditDist(str1, str2, len(str1)-1, len(str2)-1);
}

我们根据前面的推导（四个方案）来实现 shortestEditDist：

// 我能算出子串 str1[0,i] 转换为 str2[0,j] 的最小编辑距离，其中 0 <= i < n，0 <= j < m
// 实现方式：用 shortestEditDist(str1, str2, i-1, j-1) 来求解  shortestEditDist(str1, str2, i, j)
// 注意：前面推导时是从 i,j -> i+1,j+1，本质是一样的
func shortestEditDist(str1, str2 string, i, j int) int {
	// 考虑具体情况之前，先考虑递归函数的终止条件
	if i == -1 && j == -1 {
		// 两个都是空串，无需做任何处理
		return 0
	}

	if j == -1 {
		// str2 的子串是空串，str1 的子串[0,i] 只能采用删除操作才能转为 str2 的子串
		return i + 1
	}

	if i == -1 {
		// str1 的子串是空串，此时只能采用插入操作才能转为 str2 的子串
		return j + 1
	}

	// 一般情况，根据我们前面的讨论，有四种情况

	// 情况1：当前两个字符相同
	// 方案一
	if str1[i] == str2[j] {
		// 两个字符相同，先将 str1[0,i-1] 转成 str2[j-1]，然后本步骤啥也不做
		return shortestEditDist(str1, str2, i-1, j-1)
	}
	
	// 情况2：两个字符不同，有三种情况
	// 因为我们不知道本步骤到底采用什么方案操作步数最少，所以只能都尝试一遍，然后取最小值

	// 方案二：先用 str1[0,i-1] 转换出 str2[0,j]，再删除 str1[i]
	c1 := shortestEditDist(str1, str2, i-1, j) + 1

	// 方案三：先用 str1[0,i] 转换出 str2[0,j-1]，再在后面插入 str2[j] 字符
	c2 := shortestEditDist(str1, str2, i, j-1) + 1

	// 方案四：先用 str1[0,i-1] 转换出 str2[0,j-1]，再将 str1[i] 替换成 str2[j]
	c3 := shortestEditDist(str1, str2, i - 1, j - 1) + 1

	// 取三种情况代价最小的
	return minInt(c1, c2, c3)
}

如此就求出来了。

有研究过最小编辑距离的同学可能知道最小编辑距离可以通过动态规划解决，性能更高。

本文之所以使用暴力递归，因为一方面它和动态规划的思路本质是一样的，都是递推（或说归纳法）解题。会动态规划的同学很容易将暴力递归改造成动态规划，而不会的，看递归写法要比看动态规划写法直观明白得多。

初识递归思想的同学觉得这玩意不可思议，咋在不知不觉中就把结果求出来了呢？

其实它就是我们在高中学的那个强大而陌生的数学归纳法，它要求问题具备三个特性：

1. 一个集合和它的任意子集具有相同的模式；
2. 可以通过子集 \(S_n\) 的解求 \(S_{n+1}\) 的解；
3. 能够知道初始值（如 n=0）的解；

它的思想很简单：既然能够通过 \(S_n\) 的解求 \(S_{n+1}\) 的解，而我们又知道 \(S_0\) 的解，那一定能知道 \(S_1\) 的解，进而知道 \(S_2\) ......

有一点需要注意的是，我们在前面推导（递推）的时候，是通过 \(S_n\) 的解推导 \(S_{n+1}\) 的解（逻辑上是先考虑 \(S_n\) ），而在写递归函数的时候恰恰是反过来的：我们是先考虑 \(S_{n+1}\)，在处理过程中发现需要借助 \(S_{n}\) 来求解。而写在递归函数开头的函数终止条件恰恰就是递推（或说数学归纳法）中的初始值。

总结

虽然推导矩形面积和求解字符串最小编辑距离在逻辑上存在很大差别，但在思维模式上存在很多相似性：

1. 先定义清楚问题（什么是面积；什么是编辑距离）；
2. 用具体实例深入理解和挖掘问题（50*100 的矩形；"abcd" 和 "acdb" 两个字符串）；
3. 将求解对象参数化（矩形的长 l、宽 w；最小编辑距离中的 i、j）；
4. 将未知解符号化（面积 S；最小编辑距离 N）；
5. 将符号和参数组合成新的复合符号（函数。比如面积中的 S(l,w)；编辑距离中的 N(str1,str2,i,j)），给问题和解建立初步的关系；
6. 通过观察、试验，探求不同参数对解的影响（矩形边长加倍让面积加倍；可以用 str1[n-1] -> str2[m-1] 的解求 str1[n] -> str2[n] 的解）；
7. 泛化第 6 步，得出最终解；