我認(rèn)為標(biāo)題中的幾個(gè)名詞是有千絲萬(wàn)縷的聯(lián)系搭综，而且作為一名計(jì)算機(jī)科學(xué)的學(xué)習(xí)者，特別是算法領(lǐng)域划栓， 深刻的理解這些名詞背后的思想兑巾， 是非常重要的。
將原始問題拆解成子問題的方式忠荞，這在計(jì)算機(jī)領(lǐng)域是非常重要的一種解決問題的方式蒋歌。 因?yàn)橛?jì)算機(jī)非常的擅長(zhǎng)解決重復(fù)的問題。 所以如果一個(gè)問題可以被劃分成子問題委煤， 通過迭代子問題堂油， 即可求解原問題， 這也正是計(jì)算機(jī)所擅長(zhǎng)的碧绞。
看看那些經(jīng)典的算法： 二分查找府框，二叉搜索樹查找，歸并排序讥邻，快速排序迫靖，分治， 動(dòng)態(tài)規(guī)劃兴使，深度優(yōu)先搜索系宜， 都是通過原始問題拆分成子問題的方式求解。
遞歸作為計(jì)算機(jī)語(yǔ)言的一種基本而又非常重要的編程范式鲫惶，掌握它是非常重要的蜈首。 面對(duì)重復(fù)的問題，它可以優(yōu)雅而又簡(jiǎn)潔求解重復(fù)的問題。 它可以解決最典型的問題就是： 遞推式欢策。記得在大一的時(shí)候吆寨， c語(yǔ)言書本上第一次介紹了遞歸，通過漢諾塔的例子來介紹的踩寇。 解決漢諾塔問題的核心思想就在于： 將規(guī)模為n的問題拆解為規(guī)模為n-1的問題啄清，然后推導(dǎo)出遞推式。 遞歸可以是一種編程手段俺孙，可以非忱弊洌快捷的實(shí)現(xiàn)遞推式。
斐波那契數(shù)列
最典型和簡(jiǎn)單的遞推式就是斐波那契數(shù)列睛榄， 在面試題目中荣茫，它可是榜上有名的，它也通常是動(dòng)態(tài)規(guī)劃算法入門的經(jīng)典例子场靴。
斐波那契數(shù)列是非常有意思的一個(gè)遞推式啡莉。 很多問題都可以直接轉(zhuǎn)化成斐波那契數(shù)列： 如下幾個(gè)問題，都可以轉(zhuǎn)化成斐波那契數(shù)列
1.青蛙跳臺(tái)階的問題：有n臺(tái)階旨剥，每次青蛙可以選擇跳1個(gè)臺(tái)階或者2個(gè)臺(tái)階咧欣，求爬階梯的方式數(shù)
2.找零問題：一個(gè)商店只有1元和2元硬幣，對(duì)于n元轨帜，有多少種找零方法魄咕？
3.一對(duì)剛出生的兔子(一公一母)被放到島上，每對(duì)兔子出生兩個(gè)月之后才開始繁殖后代蚌父。在兔子出生兩個(gè)月后哮兰，每對(duì)兔子在每個(gè)月都將繁殖一對(duì)新的兔子。假定兔子不會(huì)死去苟弛，找出n個(gè)月后島上兔子的對(duì)數(shù)
以上三個(gè)問題奠蹬，都可以直接轉(zhuǎn)化成斐波那契數(shù)列解決。
經(jīng)典算法
下面再看看一些經(jīng)典的算法嗡午， 它們是如何用子問題的方式去設(shè)計(jì)算法的。
分治
先看看分治相關(guān)的算法：
最經(jīng)典是二分查找算和二叉搜索樹的查找冀痕， 當(dāng)然還有合并排序算法和快速排序算法荔睹， 它們的基本思想都是分而治之， 先將一個(gè)問題拆解成兩個(gè)子問題言蛇，再將求解后的子問題轉(zhuǎn)化成原問題僻他。
對(duì)于分治算法來說， 1分為2是最經(jīng)典的腊尚，當(dāng)然還可以1分為3吨拗， 甚至1分為4， 當(dāng)然如何劃分， 這個(gè)看子問題怎么定義劝篷。
動(dòng)態(tài)規(guī)劃
再看看經(jīng)典的動(dòng)態(tài)規(guī)劃算法：
這是一類算法思想哨鸭， 有著非常廣泛的應(yīng)用場(chǎng)景。 如果一個(gè)問題可以劃分成子問題娇妓， 那么就得考慮可能可以用動(dòng)態(tài)規(guī)劃思想像鸡。 上面已經(jīng)提到了， 動(dòng)態(tài)規(guī)劃的最大的特點(diǎn)之一就是： 存在重疊子問題哈恰。 既然動(dòng)態(tài)規(guī)劃最基本的思想之一是通過子問題求解只估， 那么動(dòng)態(tài)規(guī)劃可以采用遞歸來實(shí)現(xiàn)， 并且在每次遞歸的過程中着绷， 把已經(jīng)求解的子問題記憶下來蛔钙， 這樣就不需要重復(fù)的求解子問題了。
下面列出幾個(gè)比較典型的動(dòng)態(tài)規(guī)劃的問題：
1.一個(gè)字符串的最長(zhǎng)遞增子序列
2.兩個(gè)字符串的最長(zhǎng)公共子串
3.最經(jīng)典的背包問題：給定n個(gè)重量為w1,w2...wn荠医，價(jià)值為v1, v2...vn的物品和一個(gè)承重量為W的背包吁脱，求這些物品中最有價(jià)值的一個(gè)子集，并且能夠裝到背包中子漩。
4.硬幣找零問題：現(xiàn)有硬幣1元豫喧，2元，5元(假設(shè)每種硬幣的數(shù)量有無窮個(gè))幢泼，對(duì)于n元找零的方式有多少紧显？
既然動(dòng)態(tài)規(guī)劃是用于劃分子問題的。 那么對(duì)于動(dòng)態(tài)規(guī)劃來說缕棵，劃分子問題的方式有多少種呢孵班。 在劉汝佳和黃亮的《算法藝術(shù)與信息學(xué)競(jìng)賽》這本書中，我認(rèn)為歸納的非常好：
根據(jù)原問題所依賴的子問題的數(shù)目招驴，和子問題所依賴的其它子問題的數(shù)目篙程， 將動(dòng)態(tài)規(guī)劃方程式分類為四種。
具體可以參考-《算法藝術(shù)與信息學(xué)競(jìng)賽》——?jiǎng)⑷昙驯鹄澹S亮
總結(jié)?
通過子問題的方式去求解問題虱饿，這是一種求解問題的基本思想之一。 由于原始問題可能比較復(fù)雜或者無序触趴， 通過排列組合的方式將原始問題拆分成子問題氮发， 讓問題變得更加清晰和簡(jiǎn)單。 所以冗懦，通過子問題的方式爽冕， 是解決問題的一種通用的思想， 在不同的算法場(chǎng)景披蕉，有不同的應(yīng)用颈畸。
而計(jì)算機(jī)天然的非常適合解決重復(fù)的問題乌奇。 而遞歸作為一種基本和非常重要的編程范式，可以非常優(yōu)雅和簡(jiǎn)潔的寫出代碼眯娱。
所有的遞推式都可以基于計(jì)算機(jī)的遞歸進(jìn)行實(shí)現(xiàn)礁苗。
分治和動(dòng)態(tài)規(guī)劃是解決子問題的重要算法形式，當(dāng)然區(qū)分這兩個(gè)算法的特征就是： 是否有重疊子問題困乒。 對(duì)于部分子問題寂屏， 分治和動(dòng)態(tài)規(guī)劃無法解決， 這時(shí)候就可以采用搜索算法娜搂， 基本上所有的問題都可以采用搜索來解決迁霎， 它是一種更為通用的算法了。
學(xué)習(xí)資料推薦
我認(rèn)為在學(xué)習(xí)計(jì)算機(jī)的過程中百宇，深入的理解這些概念是非常重要的考廉，特別是在算法設(shè)計(jì)領(lǐng)域， 如果深刻的掌握這些概念携御， 學(xué)習(xí)起來會(huì)事倍功半昌粤。 下面我會(huì)介紹一些基本的學(xué)習(xí)資料：
我覺得可以從最基本的遞歸和遞推開始學(xué)習(xí)：
關(guān)于遞推式，推薦一本書:《離散數(shù)學(xué)及其應(yīng)用》-Keneth H. Rosen啄刹， 可以重點(diǎn)關(guān)注 第八章-高級(jí)計(jì)數(shù)技術(shù)涮坐， 最好把相關(guān)的習(xí)題刷一遍， 并且編程實(shí)現(xiàn)遞推式誓军。
關(guān)于分治和動(dòng)態(tài)規(guī)劃袱讹，這部分書籍其實(shí)是比較多的，我先推薦一本比較基礎(chǔ)的：《算法設(shè)計(jì)與分析基礎(chǔ)》——Anany Levitin昵时。 先把該書經(jīng)典的題目過一遍捷雕。 紙上談兵終覺淺， 建議在學(xué)習(xí)的過程中壹甥， 要加強(qiáng)實(shí)踐救巷， 推薦一個(gè)比較好的做題網(wǎng)站LeetCode。
動(dòng)態(tài)規(guī)劃的高階進(jìn)階者句柠，推薦一本神書： 《算法藝術(shù)與信息學(xué)競(jìng)賽》浦译， 這本書的題目非常有意思，并且難度都不低溯职。 如果能吃透了管怠， 離傳說中的大神就不遠(yuǎn)了。
最后： 對(duì)于學(xué)習(xí)計(jì)算機(jī)來說缸榄，唯一的捷徑就是：一定要編程編程編程，然后總結(jié)總結(jié)總結(jié)祝拯！
