矩形面積

小學(xué)課上我們就學(xué)過(guò)矩形的面積等于長(zhǎng)乘以寬。

但活了幾十年，你有沒(méi)有想過(guò)：矩形面積為啥等于長(zhǎng)乘以寬？

或者說(shuō)先人們?yōu)楹螌⒕匦蔚拿娣e定義為長(zhǎng)乘以寬？

（繼續(xù)之前，請(qǐng)先忘掉矩形面積等于長(zhǎng)乘以寬這個(gè)“簡(jiǎn)單”的知識(shí)）。

時(shí)光倒退幾千年，小林是個(gè)好奇心極強(qiáng)的農(nóng)夫，某天閑來(lái)無(wú)事，端著一杯茶盯著自家一塊地，就像下面這形狀：

小林突然想搞清楚這塊地有多大。于是他用尺子量了量：

他發(fā)現(xiàn)這塊地長(zhǎng)邊是 100 米，短邊是 50 米。小林分別給這兩個(gè)邊起了個(gè)名字：長(zhǎng)（長(zhǎng)邊）、寬（短邊）。

因而現(xiàn)在可以說(shuō)這塊土地大小是長(zhǎng) 100 寬 50。

但小林那該死的好奇心對(duì)這個(gè)結(jié)果并不滿意：它想知道這么大的矩形所圍出來(lái)的區(qū)域（陰影部分）到底是多大——它想用一個(gè)數(shù)字來(lái)表達(dá)這個(gè)區(qū)域。

小林現(xiàn)在還不知道這個(gè)長(zhǎng) 100 寬 50 的矩形區(qū)域到底如何用數(shù)字表示——但到目前為止，這不重要，重要的是先給它起個(gè)名字。

名字叫什么都行，不過(guò)最好能直觀，比如區(qū)域、面積——不妨就叫面積吧。

另外小林想求解的是通用矩形的面積（而不是長(zhǎng) 100 寬 50 的”這個(gè)“矩形），所以他決定用一些符號(hào)來(lái)通用地表示矩形的長(zhǎng)和寬。不妨用 l（或者別的什么符號(hào)都行）代表長(zhǎng)，用 w 代表寬。

現(xiàn)在問(wèn)題變成：求長(zhǎng) l 寬 w 的矩形的面積是多少？

答案是：不知道！

到目前為止，小林的腦袋里的數(shù)學(xué)知識(shí)只有數(shù)字（自然數(shù)）、加、減和乘——面對(duì)這個(gè)陌生的”面積“概念，他一籌莫展。

人類(lèi)有個(gè)天生的”優(yōu)點(diǎn)“：善于自欺欺人。

我們不知道矩形面積是多少對(duì)不對(duì)？但可以假裝知道啊！

就像我們給矩形的長(zhǎng)和寬符號(hào)化一樣，我們也可以給面積一個(gè)符號(hào)。

給什么符號(hào)無(wú)所謂，X、Y、面、# 都行——不妨管它叫 S 吧（雖然后人總是從語(yǔ)言歷史的角度來(lái)考證符號(hào)的含義，但實(shí)際上給它什么符號(hào)真的無(wú)所謂）。

現(xiàn)在小林好像多了一點(diǎn)知識(shí)：知道了長(zhǎng) l 寬 w 的矩形的面積是 S。

但實(shí)際上他又什么都不知道——其實(shí)不然，他憑經(jīng)驗(yàn)感覺(jué)這個(gè) S 和 l、w 有關(guān)系（有什么關(guān)系還不清楚）。

為了表示這個(gè)”重大“的發(fā)現(xiàn)（S、l、w 之間存在某種關(guān)系），**小林給出如下縮寫(xiě)：S(l,w)**。

（用其它任何縮寫(xiě)都行，比如 S[l,w]、l,w -> S 等等，我們之所以用 S(l,w) 純屬個(gè)人偏好。）

S(l,w) 和 S 這兩種表達(dá)其實(shí)是一個(gè)意思，都是表示矩形的面積，只不過(guò)前者多了進(jìn)一步的含義：矩形的面積和長(zhǎng) l、寬 w 多少存在某種關(guān)系。

接下來(lái)小林自然就會(huì)想：它們到底存在什么關(guān)系呢？

他低頭思考了半天不得其解。

就在小林快放棄的時(shí)候，他的眼角余光瞟向那一畝三分地，小林想：既然它們存在關(guān)系，那我就試著改變長(zhǎng)和寬，看看面積會(huì)發(fā)生什么變化？

首先，他把長(zhǎng) l 加倍：

小林發(fā)現(xiàn)，長(zhǎng)加倍后，面積也明顯加倍了，于是得到如下等式：

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

有點(diǎn)意思！

接下來(lái)將長(zhǎng)保持不變，寬加倍試試：

面積同樣加倍了：

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

小林覺(jué)得看到希望了！

于是他拿起樹(shù)枝在地上畫(huà)起來(lái)——小林發(fā)現(xiàn)，無(wú)論長(zhǎng)、寬增加（或減少）多少倍，面積都跟著增加（或減少）一樣的倍數(shù)。于是小林寫(xiě)下了如下式子：

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

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

表示任意數(shù)。上面的式子是說(shuō)：我們可以將矩形的長(zhǎng)拆分成兩個(gè)任意數(shù)（#、l）的乘積，然后將其中一個(gè)數(shù)從括號(hào)里面拿出來(lái)。對(duì)于寬也是如此。

接下來(lái)就要發(fā)揮人類(lèi)的推理能力了。

S(l,w) 可以寫(xiě)成 S(l*1,w)。按照上面的式子，我們可以將 l 從括號(hào)里面拿出來(lái)得到：

S(l,w) = S(l1,w) = lS(1,w)

我們?cè)賹?duì) w 做同樣的處理，得到：

S(l,w) = S(l1,w) = lS(1,w) = lS(1,w1) = lwS(1,1)

也就是說(shuō)：S(l,w) = lwS(1,1)。

至此小林得到結(jié)論：長(zhǎng) l 寬 w 的矩形的面積是 長(zhǎng) 1 寬 1 的矩形的面積的 l*w 倍。

小林并沒(méi)有得到一個(gè)絕對(duì)數(shù)，而是得到了一個(gè)相對(duì)于 長(zhǎng) 1 寬 1 的長(zhǎng)（正）方形的面積的倍數(shù)。

因?yàn)檫@個(gè)長(zhǎng) 1 寬 1 的矩形面積總是固定的，所以我們并不需要關(guān)心它的面積絕對(duì)值到底是多少，我們可以把它人為地定義為 1，那么長(zhǎng) l 寬 w 的矩形的面積就是 l*w。

這個(gè)思想很重要：我們?cè)诂F(xiàn)實(shí)世界中理所當(dāng)然地認(rèn)為是絕對(duì)值的（比如這里的面積），其實(shí)本質(zhì)上是相對(duì)值。

比如 3 米到底是多長(zhǎng)？它取決于 1 米有多長(zhǎng)。

1 分鐘有多久？它取決于 1 秒有多久。

這些作為度量參照的，我們稱(chēng)之為單位。

最底層的單位是人為定義的，而且在人類(lèi)的不同歷史時(shí)期可能有不同的定義。比如中國(guó)古代的 1 斤跟現(xiàn)代的 1 斤在重量上并不相等，但它并不妨礙兩個(gè)時(shí)代人的日常使用。

怎么做的？

在一般人看來(lái)，數(shù)學(xué)是人類(lèi)最嚴(yán)謹(jǐn)?shù)膶W(xué)科，就好像是神靈賜予人類(lèi)的先驗(yàn)禮物。

數(shù)學(xué)是嚴(yán)謹(jǐn)不假，但數(shù)學(xué)的基礎(chǔ)并不是先驗(yàn)的，而是源自人類(lèi)生活的經(jīng)驗(yàn)。

雖然數(shù)學(xué)中充斥著大量的公理、證明啥的，但數(shù)學(xué)最底層卻是一些”簡(jiǎn)單“的公設(shè)（公理。比如平面幾何學(xué)中的五大公設(shè)）。小學(xué)老師告訴我們：所謂公理，是不需要證明的（不證自明）。這個(gè)所謂的”不證自明“，說(shuō)白了就是憑經(jīng)驗(yàn)。

不但數(shù)學(xué)中最基本的公理憑經(jīng)驗(yàn)，數(shù)學(xué)中的很多求證過(guò)程也是憑經(jīng)驗(yàn)——雖然聽(tīng)起來(lái)不可思議。

我們回頭看看矩形面積的推導(dǎo)過(guò)程：

一開(kāi)始我們只是好奇心作怪，想知道如何用數(shù)來(lái)表示這么一塊矩形區(qū)域（定義問(wèn)題）。

我們發(fā)現(xiàn)自己不知道怎么求解它，沒(méi)辦法只能給它個(gè)代號(hào)（符號(hào)化）。

另外我們發(fā)現(xiàn)矩形有兩個(gè)屬性：長(zhǎng)和寬（參數(shù)化）。

經(jīng)驗(yàn)告訴我們，矩形面積跟矩形的長(zhǎng)和寬存在某種關(guān)系（關(guān)聯(lián)）。

于是我們根據(jù)經(jīng)驗(yàn)試圖去尋找它們之間到底存在哪些關(guān)系（找規(guī)律）。

經(jīng)過(guò)窮舉，我們得到了幾個(gè)很有意思的等式。

再經(jīng)過(guò)一番思考和觀察，我們發(fā)現(xiàn)這幾個(gè)等式可以泛化成一般等式（就是里面的具體數(shù)值可以變量化）。（關(guān)系泛化）

面對(duì)一般化的等式，我們利用已有知識(shí)（如 w = w * 1，即一個(gè)數(shù)乘以 1 等于它自身，這是根據(jù)乘法的定義得出的結(jié)論），最終推導(dǎo)出我們想要的東西（基于既有知識(shí)的邏輯推理）

在整個(gè)過(guò)程中，經(jīng)驗(yàn)、觀察、實(shí)驗(yàn)、符號(hào)化起到非常重要的作用。

關(guān)程序員何事？

這里涉及到我們?nèi)绾嗡伎己徒鉀Q問(wèn)題。

當(dāng)我們面臨一個(gè)陌生的（而且看起來(lái)很難的）問(wèn)題時(shí)，本能反映是摸不著頭腦。

然后就開(kāi)始抓瞎。

我們要做的是，在抓瞎之前冷靜一下，眼睛看看遠(yuǎn)方，做幾次深呼吸，然后再多想幾次問(wèn)題本身。

不要在還沒(méi)搞清楚問(wèn)題是什么之前就開(kāi)始解決問(wèn)題。

我們舉個(gè)字符串編輯距離的例子。

問(wèn)題：給定兩個(gè)字符串 str1 和 str2，求 str1 至少需要經(jīng)過(guò)多少次操作才能變成 str2。

你第一次遇到這個(gè)問(wèn)題是什么感受呢？反正我是一臉懵逼，狗咬刺猬，無(wú)處下牙。

然后的感覺(jué)是：這個(gè)問(wèn)題我好像沒(méi)怎么弄明白？

所以要先分析問(wèn)題本身。

什么叫”經(jīng)過(guò)多少次操作“？

想要知道經(jīng)過(guò)多少次操作，起碼先要知道都有什么樣的操作吧？

我們記得前面那位老農(nóng)是面對(duì)著他的一畝三分地想問(wèn)題——而我們現(xiàn)在面對(duì)的是兩個(gè)抽象的（符號(hào)）str1 和 str2。

所以接下來(lái)要將抽象的問(wèn)題具象化。

我們不妨寫(xiě)兩個(gè)具體的字符串：

str1 = "abcd"

str2 = "acdb"

現(xiàn)在變成了具體的問(wèn)題：怎樣通過(guò)最少的操作將字符串"abcd"變成"acdb"？

這個(gè)問(wèn)題其實(shí)分兩部分：

怎樣的操作？最少的操作？

一個(gè)字符串想變成另一個(gè)字符串，它總要一個(gè)字符一個(gè)字符地處理吧（你不可能連看都不看某個(gè)字符一眼就能做出正確決定）。

所以”操作“這個(gè)概念就變成了”一個(gè)字符怎樣變成另一個(gè)字符“的問(wèn)題。

我們就看第一個(gè)字符：str1 中的 a 如何變成 str2 中的 a？

想都不用想，它倆相等，不用做任何操作——不做任何操作本身就是一種操作類(lèi)型。

然后我們看看第二個(gè)字符：str1 中的 b 如何變成 str2 中的 c？

它倆不一樣，所以必須做些行動(dòng)才行。

一種方案是，將 b 替換成 c。

第二種方案是，直接將 b 刪除掉，讓它后面的字符來(lái)應(yīng)對(duì) c 這個(gè)字符。

第三種方案是，在 a 和 b 之間插入 c（將 b 挪到后面去）。

沒(méi)有其他方案了。

至此我們搞明白了所謂”操作“到底是什么：啥也不做、替換、刪除、插入，一共四種。

然后我們?cè)侔涯莻€(gè)恐怖的修飾語(yǔ)”最少的“加上去——你會(huì)發(fā)現(xiàn)此時(shí)頭又大了。

如果不限制”最少“，其實(shí)很好辦，最無(wú)腦的做法就是先把 str1 中的字符全刪掉，然后再一股腦把 str2 中的每個(gè)字符挨個(gè)插入即可，操作步數(shù)是 n + m（兩個(gè)字符串長(zhǎng)度之和）。

這個(gè)最無(wú)腦的解法雖然無(wú)用，但它揭示了該問(wèn)題的最大操作步數(shù)是 n+m，所以如果你整出的解比它還大，那肯定不對(duì)了。

我們?cè)倩氐缴厦娴木唧w字符串：怎樣通過(guò)最少的操作將字符串"abcd"變成"acdb"？

我們一個(gè)一個(gè)嘗試。

其中一種方案是：第一個(gè) a 保持不變，刪掉第二個(gè) b，最后在 d 后面插入 b，操作步數(shù)是 2。

然后我們又人肉嘗試了其它方案，發(fā)現(xiàn)所有方案中最小的就是 2。

然而，問(wèn)題好像并沒(méi)有什么進(jìn)展——我們?nèi)匀徊恢廊绾吻蟮米钌俨綌?shù)（除了人肉）。

如果我們的思路一直停留在具象的具體問(wèn)題上，便不太可能得到問(wèn)題的解。

人類(lèi)區(qū)別于其他動(dòng)物的地方在于，人類(lèi)能夠?qū)⒕呦蟮氖挛铮ìF(xiàn)象）提升成抽象的符號(hào)，進(jìn)而形成思維模型（這也正是數(shù)學(xué)的奧秘，現(xiàn)在你應(yīng)該能夠理解數(shù)學(xué)家為啥那么喜歡玩符號(hào)了）。

將問(wèn)題具象化有助于我們深刻理解問(wèn)題本身，現(xiàn)在是時(shí)候讓思維從具象回到抽象層面了。

我們先對(duì)字符串本身做抽象化表述。

字符串就是字符序列，它的本質(zhì)就是集合（外加了個(gè)限制：順序相關(guān)，即里面的字符有特定順序）。

如何通過(guò)最少操作步數(shù)將長(zhǎng)度為 n 的字符序列 {x,y,z?}n 轉(zhuǎn)換成長(zhǎng)度為 m 的字符序列 {x′,y′,z′?}m？

答案是：不知道！

那位農(nóng)夫在求不出面積的時(shí)候做了個(gè)驚人的舉動(dòng)：給它個(gè)符號(hào)！

我們也這么辦。

我們假設(shè) {x,y,z?}n -> {x′,y′,z′?}m 的最小編輯距離是 N（管它怎么求的）。

跟農(nóng)夫?qū)?S 換成 S(l,w) 以體現(xiàn)面積和邊長(zhǎng)的關(guān)系一樣，我們也將參數(shù)放進(jìn)去：

N(str1, str2)

這個(gè)組合符號(hào)是說(shuō)：它能算出字符串 str1轉(zhuǎn)換為 str2 的最少操作步數(shù)（最小編輯距離）。

至于它怎么算的，我們暫時(shí)不關(guān)心。

這玩意是不是像極了編程中的接口？

作為程序員，你可能覺(jué)得這個(gè) N 太丑了，那我們換個(gè)”人性化“點(diǎn)的名字：shortestEditDist(str1, str2)。

然后——我們盯著這奇怪的符號(hào)思考了半天，一籌莫展！

符號(hào)本身并不能告訴我們更多，我們必須開(kāi)動(dòng)推理的馬達(dá)去加工符號(hào)。

對(duì)于集合類(lèi)型問(wèn)題，我們常用的一種思維模式是：看能否通過(guò)子集的解推出父集的解。

具體地，對(duì)于”串“類(lèi)的問(wèn)題，假如我們已經(jīng)知道某個(gè)子串的解，看能否通過(guò)這個(gè)子串推出某個(gè)父串的解。

作這種解題假設(shè)的依據(jù)是：子串和父串具有相同的模式。

假設(shè)我們已經(jīng)知道了 str1 中子串 [0,i] 轉(zhuǎn)換成 str2 中子串 [0,j] 的最少操作步數(shù)是 M（先不管怎么算出來(lái)的），能不能求出 str1 中子串 [0,i+1] 轉(zhuǎn)換成 str2 中子串 [0,j+1] 的最少操作步數(shù)？

可以吧？它其實(shí)就是在原來(lái)的基礎(chǔ)上各加了一個(gè)字符——一個(gè)字符我們是能搞定的。

有了這個(gè)發(fā)現(xiàn)，我們先修正一下我們的組合符號(hào)（函數(shù)聲明），將其改成：

shortestEditDist(str1, str2, i, j)

意思變成：我能求子串 str1[0,i] -> str2[0,j] 的最小編輯距離 M（管它怎么求呢，先放出大話再說(shuō)）。

現(xiàn)在的問(wèn)題變成：如何通過(guò)子串 str1[0,i] -> str2[0,j] 的最小編輯距離 M 推導(dǎo)子串 str1[0,i+1] -> str2[0,j+1] 的編輯距離？

我們假設(shè) str1 的第 i+1 位的字符是 x（表示未知的某個(gè)字符），str2 的 第 j+1 位的字符是 y（另一個(gè)未知字符），如果 x 等于 y，則不用做任何操作，即最少操作步數(shù)仍然是 M；如果 x 不等于 y，則必須通過(guò)替換、刪除、插入中的一種操作才能實(shí)現(xiàn)轉(zhuǎn)換，此時(shí)最少操作步數(shù)是 M+1。

問(wèn)題是，當(dāng) x 不等于 y 的時(shí)候，到底采用三種中的哪種操作呢？

三種操作的區(qū)別在于對(duì)后面字符的影響：

采用刪除方案，則下一步要處理的是 str1 的 i+2 位置的字符和 str2 的 j+1 位置的字符（刪除的意思是試圖用源字符串下一個(gè)位置的字符來(lái)解決目標(biāo)字符串當(dāng)前位置的字符）；采用插入方案，下一步要處理的是 str1 的 i+1 位置的字符和 str2 的 j+2 位置的字符（插入的意思是直接在當(dāng)前位置新生成目標(biāo)字符串的字符，將原本該位置的字符留下來(lái)用以解決目標(biāo)字符串的下一個(gè)字符）；采用替換方案：則是一對(duì)一抵消，下一步處理的是 str1 的 i+2 位置字符和 str2 的 j+2 位置的字符；

事實(shí)是：我們根本不知道哪種方案能使整體操作步數(shù)最少——除非一個(gè)一個(gè)嘗試。

那就一個(gè)一個(gè)試吧！

我們寫(xiě)一下代碼：

// 我能算出子串 str1[0,i] 轉(zhuǎn)換為 str2[0,j] 的最小編輯距離，其中 0 <= i < n，0 <= j < mfunc shortestEditDist(str1, str2 string, i, j int) int { // 還沒(méi)想好怎么實(shí)現(xiàn)...}

// 求 str1 轉(zhuǎn)成 str2 的最小編輯距離func EditDistance(str1, str2 string) int { // 既然你做了那樣的聲明，我就這樣用 // 算不出來(lái)唯你是問(wèn)！ return shortestEditDist(str1, str2, len(str1)-1, len(str2)-1);}

既然吹了牛，終究還是要兌現(xiàn)它。

現(xiàn)在我們想想 shortestEditDist 具體怎么實(shí)現(xiàn)。

根據(jù)前面的思路，我們可以用 shortestEditDist(str1, str2, i-1, j-1) 來(lái)求解 shortestEditDist(str1, str2, i, j)。

// 我能算出子串 str1[0,i] 轉(zhuǎn)換為 str2[0,j] 的最小編輯距離，其中 0 <= i < n，0 <= j < m// 實(shí)現(xiàn)方式：用 shortestEditDist(str1, str2, i-1, j-1) 來(lái)求解 shortestEditDist(str1, str2, i, j)// 也就是暴力遞歸func shortestEditDist(str1, str2 string, i, j int) int { // 考慮具體情況之前，先考慮遞歸函數(shù)的終止條件 if i == -1 && j == -1 { // 兩個(gè)都是空串，無(wú)需做任何處理 return 0 } if j == -1 { // str2 的子串是空串，str1 的子串[0,i] 只能采用刪除操作才能轉(zhuǎn)為 str2 的子串 return i + 1 } if i == -1 { // str1 的子串是空串，此時(shí)只能采用插入操作才能轉(zhuǎn)為 str2 的子串 return j + 1 } // 一般情況，根據(jù)我們前面的討論，有四種情況 // 情況1：當(dāng)前兩個(gè)字符相同 if str1[i] == str2[j] { // 兩個(gè)字符相同，先將 str1[0,i-1] 轉(zhuǎn)成 str2[j-1]，然后本步驟啥也不做 return shortestEditDist(str1, str2, i-1, j-1) } // 情況2：兩個(gè)字符不同，有三種情況 // 因?yàn)槲覀儾恢辣静襟E到底采用什么方案才會(huì)讓整體操作步數(shù)最少，所以只能都嘗試一遍，然后取最小值 // 注意：我們?cè)谇懊媸菑淖笸宜伎紗?wèn)題的（往后推），而這里遞歸求解的方向是相反的（往前推），思維要稍微轉(zhuǎn)換下 // 選擇1：先用 str1[0,i-1] 轉(zhuǎn)換出 str2[0,j]，再刪除 str1[i] c1 := shortestEditDist(str1, str2, i-1, j) + 1 // 選擇2：先用 str1[0,i] 轉(zhuǎn)換出 str2[0,j-1]，再在后面插入 str2[j] 字符 c2 := shortestEditDist(str1, str2, i, j-1) + 1 // 選擇3：先用 str1[0,i-1] 轉(zhuǎn)換出 str2[0,j-1]，再將 str1[i] 替換成 str2[j] c3 := shortestEditDist(str1, str2, i - 1, j - 1) + 1 // 取三種情況代價(jià)最小的 return minInt(c1, c2, c3)}

如此就求出來(lái)了。

有研究過(guò)最小編輯距離的同學(xué)可能知道最小編輯距離可以通過(guò)動(dòng)態(tài)規(guī)劃解決，性能更高。 本文之所以使用暴力遞歸，因?yàn)橐环矫嫠蛣?dòng)態(tài)規(guī)劃的思路本質(zhì)是一樣的，都是遞推（或說(shuō)歸納法）解題。會(huì)動(dòng)態(tài)規(guī)劃的同學(xué)很容易將暴力遞歸改造成動(dòng)態(tài)規(guī)劃，而不會(huì)的，看遞歸寫(xiě)法要比看動(dòng)態(tài)規(guī)劃寫(xiě)法直觀明白得多。

初識(shí)遞歸思想的同學(xué)覺(jué)得這玩意不可思議，咋在不知不覺(jué)中就把結(jié)果求出來(lái)了呢？

其實(shí)它就是我們?cè)诟咧袑W(xué)的那個(gè)強(qiáng)大而陌生的數(shù)學(xué)歸納法，它要求問(wèn)題具備三個(gè)特性：

一個(gè)集合和它的任意子集具有相同的模式；可以通過(guò)子集 Sn 的解求 Sn+1 的解；能夠知道初始值（如 n=0）的解；

它的思想很簡(jiǎn)單：既然能夠通過(guò) Sn 的解求 Sn+1 的解，而我們又知道 S0 的解，那一定能知道 S1 的解，進(jìn)而知道 S2 ......

有一點(diǎn)需要注意的是，我們?cè)谇懊嫱茖?dǎo)（遞推）的時(shí)候，是通過(guò) Sn 的解推導(dǎo) Sn+1 的解（邏輯上是先考慮 Sn ），而在寫(xiě)遞歸函數(shù)的時(shí)候恰恰是反過(guò)來(lái)的：我們是先考慮 Sn+1，在處理過(guò)程中發(fā)現(xiàn)需要借助 Sn 來(lái)求解。而寫(xiě)在遞歸函數(shù)開(kāi)頭的函數(shù)終止條件恰恰就是遞推（或說(shuō)數(shù)學(xué)歸納法）中的初始值。

總結(jié)

雖然推導(dǎo)矩形面積和求解字符串最小編輯距離在邏輯上存在很大差別，但在思維模式上存在很多相似性：

先定義清楚問(wèn)題（什么是面積；什么是編輯距離）；用具體實(shí)例深入理解和挖掘問(wèn)題（50*100 的矩形；"abcd" 和 "acdb" 兩個(gè)字符串）；將求解對(duì)象參數(shù)化（矩形的長(zhǎng) l、寬 w；最小編輯距離中的 i、j）；將未知解符號(hào)化（面積 S；最小編輯距離 N）；將符號(hào)和參數(shù)組合成新的復(fù)合符號(hào)（函數(shù)。比如面積中的 S(l,w)；編輯距離中的 N(str1,str2,i,j)），給問(wèn)題和解建立初步的關(guān)系；通過(guò)觀察、試驗(yàn)，探求不同參數(shù)對(duì)解的影響（矩形邊長(zhǎng)加倍讓面積加倍；可以用 str1[n-1] -> str2[m-1] 的解求 str1[n] -> str2[n] 的解）；泛化第 6 步，得出最終解；

來(lái)源：https:///linvanda/p/16460103.html