先來個(gè)游戲
我們先來做一個(gè)游戲摔笤。第一個(gè)人先從1和2中挑一個(gè)數(shù)字，第二個(gè)人可以在對(duì)方的基礎(chǔ)上選擇加1蛤高，或者加2蚣旱。然后又輪到了第一個(gè)人，他可以再次選擇加1戴陡，或者加2塞绿，之后把選擇權(quán)交給對(duì)方。就這樣雙方交替地選擇加1或者加2恤批，誰要是正好加到20异吻，誰就贏了。用什么策略保證一定能贏喜庞？
為了方便你理解诀浪，我們舉一個(gè)實(shí)際的例子，當(dāng)然加到20的時(shí)間太長(zhǎng)延都，我們假設(shè)加到10雷猪。假如我讓你先選，你選了2晰房。接下來我選擇加2求摇，這樣我加到了4酵颁，然后你選擇加1，你加到了5月帝，這時(shí)我還會(huì)選擇加2躏惋，就加到了7。接下來嚷辅，不論你選擇加1到8簿姨，還是加2到9，我都能加到10簸搞，因此我贏定了扁位。當(dāng)然，你可能覺得先作選擇的人吃虧趁俊，那么這次我先來域仇。我選擇1，你可能會(huì)選擇加2到3寺擂，然后我選擇加1到4暇务。接下來，假如你選擇加2到6怔软，我會(huì)選擇加1到7垦细，這又回到第一次最后的狀態(tài)了，我還是贏了挡逼。
可能你已經(jīng)從上面的例子中想清楚這道題里面的技巧了括改，如果你還沒有想清楚，我再等你五秒鐘……好了家坎，我們回來講講這道題嘱能。其實(shí)如果僅僅是搶10，情況并不復(fù)雜虱疏，你即使想不清楚它的道理惹骂，試幾次也能找到規(guī)律，但是如果是搶20订框，情況就復(fù)雜多了析苫。如果是搶30兜叨，搶50呢穿扳？就不能通過窮舉法這種笨辦法解決問題了，就必須找它的規(guī)律了国旷。
可能你已經(jīng)看出來了矛物。要想搶到20，就需要搶到17跪但，因?yàn)閾尩搅?7履羞，無論對(duì)方是加1還是加2，你都可以加到20。而要想搶到17忆首，就要搶到14爱榔，以此類推，就必須搶到11糙及、8详幽、5和2。因此對(duì)于這道題浸锨，只要第一個(gè)人搶到了2唇聘，他就贏定了。這里面最核心的地方在于看清楚柱搜，無論對(duì)方選擇1還是2迟郎，你都可以讓這一輪兩個(gè)人加起來的數(shù)值等于3，于是你就可以牢牢控制整個(gè)過程了聪蘸。
遞歸
那么這道看似是智力題的面試題是要考察候選人的什么技能呢宪肖？就是對(duì)計(jì)算機(jī)遞歸思想的理解。對(duì)于一般的人健爬，讓他們數(shù)數(shù)匈庭，數(shù)到20。他們會(huì)從小往大數(shù)浑劳，但是這道題的解題思想正好相反阱持。它是要尋找20，就要先尋找17魔熏，至于怎么從17到20衷咽，方法你是知道的。接下來要尋找17蒜绽，就要尋找14镶骗，等等躲雅，這就是遞歸的思想鼎姊。
倒推與減法
上述思想其實(shí)在我們做事情的時(shí)候也經(jīng)常采用。比如我要完成一本書的出版相赁，有兩個(gè)辦法相寇，一個(gè)辦法是順序估算每一個(gè)任務(wù)的時(shí)間。首先我要在一個(gè)月內(nèi)交稿钮科，出版社要在一個(gè)月內(nèi)完成一校唤衫，然后我在某個(gè)時(shí)間完成修改，最后在某月某日出版绵脯，這是一種做法佳励。
還有一種做法是倒推休里，或者倒逼。比如我們要在"雙十一"前上市銷售赃承，那么書就必須在11月1日入庫妙黍，在10月15日開印，在10月5日定稿瞧剖，等等废境，然后倒推我交稿的時(shí)間，一校筒繁、二校完成的時(shí)間等等噩凹。
哪種工作方式更有效呢？通常是后一種毡咏。另外驮宴，如果按照后一種方式工作，你會(huì)發(fā)現(xiàn)很多事情根本不可能在規(guī)定的時(shí)間做完呕缭，那么怎么辦呢堵泽？辦法很簡(jiǎn)單，就是做減法恢总。你可以認(rèn)為迎罗，上面這種工作方法，其實(shí)和計(jì)算機(jī)思維中的遞歸在原理上是一致的片仿。
游戲升級(jí)
上面這道面試題纹安，可能有點(diǎn)過于簡(jiǎn)單，但是面試官其實(shí)還留有了兩個(gè)后手砂豌。
首先厢岂，他會(huì)問面試者，按照上述方法阳距，從一開始（以1為起點(diǎn)）加到20塔粒，有多少種不同的遞加過程？比如1筐摘，4卒茬，7，10咖熟，12圃酵，15，18球恤，20是一種辜昵；2荸镊，5咽斧，8堪置，11，14张惹，17舀锨，20又是一種。那么這樣的過程有多少種呢宛逗？這道題顯然不簡(jiǎn)單了吧坎匿？下面我再給你5秒鐘想一下。
好了雷激，5秒鐘時(shí)間過去了替蔬，我估計(jì)絕大部分人還是想不出來。事實(shí)上屎暇，面試Google的人大部分在兩分鐘內(nèi)根本想不出這道題的答案承桥，更不要說5秒鐘了。因此你如果沒有想出來根悼，不要?dú)怵H凶异，接下來我給你一講就明白了。
斐波那契數(shù)列
解這道題的技巧也在于使用遞歸挤巡，如果你從1剩彬，2，3開始找規(guī)律就難了矿卑。我們假定數(shù)到20有F（20）種不同的路徑喉恋，那么到達(dá)20這個(gè)數(shù)字，前一步只有兩個(gè)可能的情況母廷，即從18直接蹦到20瀑晒，或者從19數(shù)到20。
由于從18蹦到20徘意，和19到20苔悦，彼此是不同的，因此走到20的路徑數(shù)量椎咧，其實(shí)就是走到18的路徑數(shù)量玖详，加上走到19的路徑數(shù)量，也就是說F（20）＝F（18）＋F（19）勤讽。類似地蟋座，F(xiàn)（19）＝F（18）＋F（17）。這就是遞推公式脚牍。
最后向臀，F(xiàn)（1）只有一個(gè)可能性，就是1诸狭，F(xiàn)（2）有兩個(gè)可能性券膀，要么直接蹦到2君纫，要么從1走到2。知道了F（1）和F（2）芹彬，就可以知道F（3）蓄髓，然后再倒著推導(dǎo)回去，一直到F（20）即可舒帮。
數(shù)學(xué)比較好的朋友会喝，可能已經(jīng)看出來這是著名的斐波那契數(shù)列，如果我們認(rèn)為F（0）也等于1玩郊，那么這個(gè)數(shù)列是這樣的肢执，1（＝F（0）），1译红，2蔚万，3，5临庇，8反璃，13，21假夺，……這個(gè)數(shù)列幾乎按照幾何級(jí)數(shù)的速度增長(zhǎng)淮蜈，到了F（20），就已經(jīng)是10946了已卷。因此梧田，靠窮舉法是不可能把所有情況想清楚的。
等價(jià)性原則
在數(shù)學(xué)和計(jì)算機(jī)上侧蘸，還有一個(gè)非常重要的原則裁眯，就是等價(jià)性原則，也就是說很多問題是等價(jià)的讳癌。比如說穿稳，我再給你出一道題，如果一個(gè)樓梯有20層晌坤，你每次可以走一層或者兩層逢艘，爬到20層有多少種走法？這個(gè)問題的解骤菠，和搶20是一樣的它改，也是斐波那契數(shù)列。
總結(jié)
今天商乎，我通過一個(gè)不算太復(fù)雜的問題央拖，再一次講解了遞歸的思想，你把它理解為生活和工作中的倒逼就好了。另外鲜戒，我再一次強(qiáng)調(diào)了計(jì)算機(jī)科學(xué)和數(shù)學(xué)中的等價(jià)性原則专控，掌握了這個(gè)原則，就可以把很多問題歸結(jié)為一類問題袍啡，解決了其中的一個(gè)踩官，其他的就迎刃而解却桶。
今天給大家留兩道思考題：
- 搶40的策略境输，每個(gè)人每次可以選擇加1到4中的任何一個(gè)數(shù)字，如果你先開始颖系，你怎樣能贏嗅剖？
- 能否談?wù)勀銓?duì)工作中對(duì)倒逼的方法的體會(huì)？
轉(zhuǎn)載至：吳軍的谷歌方法論20180619
