算法思想是解決問(wèn)題的核心绍昂，萬(wàn)丈高樓起于平地，在算法中也是如此肺樟，95% 的算法都是基于這 6 種算法思想，結(jié)下了介紹一下這 6 種算法思想逻淌，幫助你理解及解決各種算法問(wèn)題么伯。

1 遞歸算法

1.1 算法策略

遞歸算法是一種直接或者間接調(diào)用自身函數(shù)或者方法的算法。

遞歸算法的實(shí)質(zhì)是把問(wèn)題分解成規(guī)目ㄈ澹縮小的同類(lèi)問(wèn)題的子問(wèn)題田柔，然后遞歸調(diào)用方法來(lái)表示問(wèn)題的解俐巴。遞歸算法對(duì)解決一大類(lèi)問(wèn)題很有效，它可以使算法簡(jiǎn)潔和易于理解硬爆。

優(yōu)缺點(diǎn)：

• 優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單易上手
• 缺點(diǎn)：遞歸算法對(duì)常用的算法如普通循環(huán)等欣舵，運(yùn)行效率較低；并且在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)缀磕、局部量等開(kāi)辟了棧來(lái)存儲(chǔ)缘圈，遞歸太深，容易發(fā)生棧溢出

1.2 適用場(chǎng)景

遞歸算法一般用于解決三類(lèi)問(wèn)題：

• 數(shù)據(jù)的定義是按遞歸定義的袜蚕。（斐波那契數(shù)列）
• 問(wèn)題解法按遞歸算法實(shí)現(xiàn)糟把。（回溯）
• 數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。（樹(shù)的遍歷牲剃，圖的搜索）

遞歸的解題策略：

• 第一步：明確你這個(gè)函數(shù)的輸入輸出遣疯，先不管函數(shù)里面的代碼什么，而是要先明白凿傅，你這個(gè)函數(shù)的輸入是什么缠犀，輸出為何什么，功能是什么聪舒，要完成什么樣的一件事辨液。
• 第二步：尋找遞歸結(jié)束條件，我們需要找出什么時(shí)候遞歸結(jié)束过椎，之后直接把結(jié)果返回
• 第三步：明確遞歸關(guān)系式室梅，怎么通過(guò)各種遞歸調(diào)用來(lái)組合解決當(dāng)前問(wèn)題

1.3 使用遞歸算法求解的一些經(jīng)典問(wèn)題

• 斐波那契數(shù)列
• 漢諾塔問(wèn)題
• 樹(shù)的遍歷及相關(guān)操作

DOM樹(shù)為例

下面以以 DOM 為例戏仓，實(shí)現(xiàn)一個(gè) document.getElementById 功能

由于DOM是一棵樹(shù)疚宇，而樹(shù)的定義本身就是用的遞歸定義，所以用遞歸的方法處理樹(shù)赏殃，會(huì)非常地簡(jiǎn)單自然敷待。

第一步：明確你這個(gè)函數(shù)的輸入輸出

從 DOM 根節(jié)點(diǎn)一層層往下遞歸，判斷當(dāng)前節(jié)點(diǎn)的 id 是否是我們要尋找的 id='d-cal'

輸入：DOM 根節(jié)點(diǎn) document 仁热，我們要尋找的 id='d-cal'

輸出：返回滿足 id='sisteran' 的子結(jié)點(diǎn)

function getElementById(node, id){}

第二步：尋找遞歸結(jié)束條件

從document開(kāi)始往下找榜揖，對(duì)所有子結(jié)點(diǎn)遞歸查找他們的子結(jié)點(diǎn)，一層一層地往下查找：

• 如果當(dāng)前結(jié)點(diǎn)的 id 符合查找條件抗蠢，則返回當(dāng)前結(jié)點(diǎn)
• 如果已經(jīng)到了葉子結(jié)點(diǎn)了還沒(méi)有找到举哟，則返回 null

function getElementById(node, id){
    // 當(dāng)前結(jié)點(diǎn)不存在，已經(jīng)到了葉子結(jié)點(diǎn)了還沒(méi)有找到迅矛，返回 null
    if(!node) return null
    // 當(dāng)前結(jié)點(diǎn)的 id 符合查找條件妨猩，返回當(dāng)前結(jié)點(diǎn)
    if(node.id === id) return node
}

第三步：明確遞歸關(guān)系式

當(dāng)前結(jié)點(diǎn)的 id 不符合查找條件，遞歸查找它的每一個(gè)子結(jié)點(diǎn)

function getElementById(node, id){
    // 當(dāng)前結(jié)點(diǎn)不存在秽褒，已經(jīng)到了葉子結(jié)點(diǎn)了還沒(méi)有找到壶硅，返回 null
    if(!node) return null
    // 當(dāng)前結(jié)點(diǎn)的 id 符合查找條件威兜，返回當(dāng)前結(jié)點(diǎn)
    if(node.id === id) return node
    // 前結(jié)點(diǎn)的 id 不符合查找條件，繼續(xù)查找它的每一個(gè)子結(jié)點(diǎn)
    for(var i = 0; i < node.childNodes.length; i++){
        // 遞歸查找它的每一個(gè)子結(jié)點(diǎn)
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}

就這樣庐椒，我們的一個(gè) document.getElementById 功能已經(jīng)實(shí)現(xiàn)了：

function getElementById(node, id){
    if(!node) return null;
    if(node.id === id) return node;
    for(var i = 0; i < node.childNodes.length; i++){
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}
getElementById(document, "d-cal");

最后在控制臺(tái)驗(yàn)證一下椒舵，執(zhí)行結(jié)果如下圖所示：

使用遞歸的優(yōu)點(diǎn)是代碼簡(jiǎn)單易懂，缺點(diǎn)是效率比不上非遞歸的實(shí)現(xiàn)约谈。Chrome瀏覽器的查DOM是使用非遞歸實(shí)現(xiàn)笔宿。非遞歸要怎么實(shí)現(xiàn)呢？

如下代碼：

function getByElementId(node, id){
    //遍歷所有的Node
    while(node){
        if(node.id === id) return node;
        node = nextElement(node);
    }
    return null;
}

還是依次遍歷所有的 DOM 結(jié)點(diǎn)棱诱，只是這一次改成一個(gè) while 循環(huán)措伐，函數(shù) nextElement 負(fù)責(zé)找到下一個(gè)結(jié)點(diǎn)。所以關(guān)鍵在于這個(gè) nextElement 如何實(shí)現(xiàn)非遞歸查找結(jié)點(diǎn)功能：

// 深度遍歷
function nextElement(node){
    // 先判斷是否有子結(jié)點(diǎn)
    if(node.children.length) {
        // 有則返回第一個(gè)子結(jié)點(diǎn)
        return node.children[0];
    }
    // 再判斷是否有相鄰結(jié)點(diǎn)
    if(node.nextElementSibling){
        // 有則返回它的下一個(gè)相鄰結(jié)點(diǎn)
        return node.nextElementSibling;
    }
    // 否則军俊，往上返回它的父結(jié)點(diǎn)的下一個(gè)相鄰元素侥加，相當(dāng)于上面遞歸實(shí)現(xiàn)里面的for循環(huán)的i加1
    while(node.parentNode){
        if(node.parentNode.nextElementSibling) {
            return node.parentNode.nextElementSibling;
        }
        node = node.parentNode;
    }
    return null;
}

在控制臺(tái)里面運(yùn)行這段代碼，同樣也可以正確地輸出結(jié)果粪躬。不管是非遞歸還是遞歸担败，它們都是深度優(yōu)先遍歷，這個(gè)過(guò)程如下圖所示镰官。

911d459419ad0aa33868ccf5c4f16c61_v2-942e712d881464b85a421387138a35db_r.jpg

實(shí)際上 getElementById 瀏覽器是用的一個(gè)哈希 map 存儲(chǔ)的提前，根據(jù) id 直接映射到 DOM 結(jié)點(diǎn)，而 getElementsByClassName 就是用的這樣的非遞歸查找泳唠。

參考：我接觸過(guò)的前端數(shù)據(jù)結(jié)構(gòu)與算法

2 分治算法

2.1 算法策略

在計(jì)算機(jī)科學(xué)中狈网，分治算法是一個(gè)很重要的算法，快速排序笨腥、歸并排序等都是基于分治策略進(jìn)行實(shí)現(xiàn)的拓哺，所以，建議理解掌握它脖母。

分治士鸥，顧名思義，就是 分而治之 谆级，將一個(gè)復(fù)雜的問(wèn)題烤礁，分成兩個(gè)或多個(gè)相似的子問(wèn)題，在把子問(wèn)題分成更小的子問(wèn)題肥照，直到更小的子問(wèn)題可以簡(jiǎn)單求解脚仔，求解子問(wèn)題，則原問(wèn)題的解則為阿子問(wèn)題解的合并舆绎。

2.2 適用場(chǎng)景

當(dāng)出現(xiàn)滿足以下條件的問(wèn)題鲤脏，可以嘗試只用分治策略進(jìn)行求解：

• 原始問(wèn)題可以分成多個(gè)相似的子問(wèn)題
• 子問(wèn)題可以很簡(jiǎn)單的求解
• 原始問(wèn)題的解是子問(wèn)題解的合并
• 各個(gè)子問(wèn)題是相互獨(dú)立的，不包含相同的子問(wèn)題

分治的解題策略：

• 第一步：分解亿蒸，將原問(wèn)題分解為若干個(gè)規(guī)模較小凑兰，相互獨(dú)立掌桩，與原問(wèn)題形式相同的子問(wèn)題
• 第二步：解決，解決各個(gè)子問(wèn)題
• 第三步：合并姑食，將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解

2.3 使用分治法求解的一些經(jīng)典問(wèn)題

• 二分查找
• 歸并排序
• 快速排序
• 漢諾塔問(wèn)題
• React 時(shí)間分片

二分查找

也稱(chēng)折半查找算法波岛，它是一種簡(jiǎn)單易懂的快速查找算法。例如我隨機(jī)寫(xiě)0-100之間的一個(gè)數(shù)字音半，讓你猜我寫(xiě)的是什么则拷？你每猜一次，我就會(huì)告訴你猜的大了還是小了曹鸠，直到猜中為止煌茬。

第一步：分解

每次猜拳都把上一次的結(jié)果分出大的一組和小的一組，兩組相互獨(dú)立

• 選擇數(shù)組中的中間數(shù)

function binarySearch(items, item) {
    // low彻桃、mid坛善、high將數(shù)組分成兩組
    var low = 0,
        high = items.length - 1,
        mid = Math.floor((low+high)/2),
        elem = items[mid]
    // ...
}

第二步：解決子問(wèn)題

查找數(shù)與中間數(shù)對(duì)比

• 比中間數(shù)低，則去中間數(shù)左邊的子數(shù)組中尋找邻眷；
• 比中間數(shù)高眠屎，則去中間數(shù)右邊的子數(shù)組中尋找；
• 相等則返回查找成功

while(low <= high) {
 if(elem < item) { // 比中間數(shù)高
  low = mid + 1
 } else if(elem > item) { // 比中間數(shù)低
  high = mid - 1
 } else { // 相等
     return mid
 }
}

第三步：合并

function binarySearch(items, item) {
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low+high)/2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

最后肆饶，二分法只能應(yīng)用于數(shù)組有序的情況改衩，如果數(shù)組無(wú)序，二分查找就不能起作用了

function binarySearch(items, item) {
    // 快排
    quickSort(items)
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low+high)/2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

// 測(cè)試
var arr = [2,3,1,4]
binarySearch(arr, 3)
// 2

binarySearch(arr, 5)
// -1

測(cè)試成功

3 貪心算法

3.1 算法策略

貪心算法驯镊，故名思義葫督，總是做出當(dāng)前的最優(yōu)選擇，即期望通過(guò)局部的最優(yōu)選擇獲得整體的最優(yōu)選擇板惑。

某種意義上說(shuō)橄镜，貪心算法是很貪婪、很目光短淺的洒放，它不從整體考慮蛉鹿，僅僅只關(guān)注當(dāng)前的最大利益滨砍，所以說(shuō)它做出的選擇僅僅是某種意義上的局部最優(yōu)往湿，但是貪心算法在很多問(wèn)題上還是能夠拿到最優(yōu)解或較優(yōu)解，所以它的存在還是有意義的惋戏。

3.2 適用場(chǎng)景

在日常生活中领追，我們使用到貪心算法的時(shí)候還是挺多的，例如：

從100章面值不等的鈔票中响逢，抽出 10 張绒窑，怎樣才能獲得最多的價(jià)值？

我們只需要每次都選擇剩下的鈔票中最大的面值舔亭，最后一定拿到的就是最優(yōu)解些膨，這就是使用的貪心算法蟀俊，并且最后得到了整體最優(yōu)解。

但是订雾，我們?nèi)稳恍枰鞔_的是肢预，期望通過(guò)局部的最優(yōu)選擇獲得整體的最優(yōu)選擇，僅僅是期望而已洼哎，也可能最終得到的結(jié)果并不一定不能是整體最優(yōu)解烫映。

例如：求取A到G最短路徑：

a271ff181554dc0236195610d65b3fde_v2-54588b7ea720de400861bc43862a69d4_r.jpg

根據(jù)貪心算法總是選擇當(dāng)前最優(yōu)選擇，所以它首先選擇的路徑是 AB噩峦，然后 BE锭沟、EG，所得到的路徑總長(zhǎng)為 1 + 5 + 4 = 10识补，然而這并不是最短路徑族淮，最短路徑為 A->C->G : 2 + 2 = 4，所以說(shuō)凭涂，貪心算法得到得并不一定是最優(yōu)解瞧筛。

那么一般在什么時(shí)候可以嘗試選擇使用貪心算法喃？

當(dāng)滿足一下條件時(shí)导盅，可以使用：

• 原問(wèn)題復(fù)雜度過(guò)高
• 求全局最優(yōu)解的數(shù)學(xué)模型難以建立或計(jì)算量過(guò)大
• 沒(méi)有太大必要一定要求出全局最優(yōu)解较幌，“比較優(yōu)”就可以

如果使用貪心算法求最優(yōu)解，可以按照以下 步驟求解 ：

• 首先白翻，我們需要明確什么是最優(yōu)解（期望）

• 然后乍炉，把問(wèn)題分成多個(gè)步驟，每一步都需要滿足：

• 可行性：每一步都滿足問(wèn)題的約束

• 局部最優(yōu)：每一步都做出一個(gè)局部最優(yōu)的選擇

• • 不可取消：選擇一旦做出滤馍，在后面遇到任何情況都不可取消

• 最后岛琼，疊加所有步驟的最優(yōu)解，就是全局最優(yōu)解

3.3 經(jīng)典案例：活動(dòng)選擇問(wèn)題

使用貪心算法求解的經(jīng)典問(wèn)題有：

• 最小生成樹(shù)算法
• 單源最短路徑的 Dijkstra 算法
• Huffman 壓縮編碼
• 背包問(wèn)題
• 活動(dòng)選擇問(wèn)題等

其中活動(dòng)選擇問(wèn)題是最簡(jiǎn)單的巢株，這里詳細(xì)介紹這個(gè)槐瑞。

活動(dòng)選擇問(wèn)題是《算法導(dǎo)論》上的例子，也是一個(gè)非常經(jīng)典的問(wèn)題阁苞。有 n 個(gè)活動(dòng)（a1,a2,…,an）需要使用同一個(gè)資源（例如教室）困檩，資源在某個(gè)時(shí)刻只能供一個(gè)活動(dòng)使用。每個(gè)活動(dòng) ai 都有一個(gè)開(kāi)始時(shí)間 si 和結(jié)束時(shí)間 fi 那槽。一旦被選擇后悼沿，活動(dòng) ai 就占據(jù)半開(kāi)時(shí)間區(qū)間 [si,fi) 。如果 [si,fi) 和 [sj,fj) 互不重疊骚灸，ai 和 aj 兩個(gè)活動(dòng)就可以被安排在這一天糟趾。

該問(wèn)題就是要安排這些活動(dòng)，使得盡量多的活動(dòng)能不沖突的舉行。例如下圖所示的活動(dòng)集合S义郑，其中各項(xiàng)活動(dòng)按照結(jié)束時(shí)間單調(diào)遞增排序蝶柿。

6d25344d55f4929775cd0b9699f02619_v2-b0e85757eb277fe9d186d49cf50a3add_r.jpg

共有 7 個(gè)活動(dòng)，它們?cè)?18 個(gè)小時(shí)內(nèi)需要占用的時(shí)間如上圖非驮，如何選擇活動(dòng)只锭，能讓這間教室利用率最高喃（能夠舉行更多的活動(dòng)）？

貪心算法對(duì)這種問(wèn)題的解決很簡(jiǎn)單的院尔，它開(kāi)始時(shí)刻開(kāi)始選擇蜻展，每次選擇開(kāi)始時(shí)間與與已選擇活動(dòng)不沖突的，結(jié)束時(shí)間又比較靠前的活動(dòng)邀摆，這樣會(huì)讓剩下的時(shí)間區(qū)間更長(zhǎng)纵顾。

image.png

• 首先 a1 活動(dòng)的結(jié)束時(shí)間最早，選擇 a1 活動(dòng)
• a1 結(jié)束后栋盹，a2 有時(shí)間沖突施逾，不可選擇，a3例获、a4 都可選擇汉额，但 a4 結(jié)束時(shí)間最早，選擇 a4
• 依次選擇時(shí)間沒(méi)有沖突的榨汤，又結(jié)束時(shí)間最早的活動(dòng)

最終選擇活動(dòng)為 a1蠕搜，a4，a5收壕，a7妓灌。為最優(yōu)解。

4 回溯算法

4.1 算法策略

回溯算法是一種搜索法蜜宪，試探法虫埂，它會(huì)在每一步做出選擇，一旦發(fā)現(xiàn)這個(gè)選擇無(wú)法得到期望結(jié)果圃验，就回溯回去掉伏，重新做出選擇。深度優(yōu)先搜索利用的就是回溯算法思想澳窑。

4.2 適用場(chǎng)景

回溯算法很簡(jiǎn)單斧散，它就是不斷的嘗試，直到拿到解照捡。它的這種算法思想颅湘，使它通常用于解決廣度的搜索問(wèn)題，即從一組可能的解中栗精，選擇一個(gè)滿足要求的解。

4.3 使用回溯算法的經(jīng)典案例

• 深度優(yōu)先搜索
• 0-1背包問(wèn)題
• 正則表達(dá)式匹配
• 八皇后
• 數(shù)獨(dú)
• 全排列

等等，深度優(yōu)先搜索我們?cè)趫D那一章已經(jīng)介紹過(guò)悲立，這里以正則表達(dá)式匹配為例鹿寨，介紹一下

正則表達(dá)式匹配

var string = "abbc"
var regex = /ab{1,3}c/
console.log( string.match(regex) )
// ["abbc", index: 0, input: "abbc", groups: undefined]

它的匹配過(guò)程：

bbf062fed9c7e9507d27d584a2b153f1_v2-286d3457d8ea9233c4b9d1f9b6e1bdd0_r.jpg

在第 5 步匹配失敗，此時(shí) b{1,3} 已經(jīng)匹配到了兩個(gè) b 正在嘗試第三個(gè) b 薪夕，結(jié)果發(fā)現(xiàn)接下來(lái)是 c 脚草。此時(shí)就需要回溯到上一步， b{1,3} 匹配完畢（匹配到了 bb ）原献，然后再匹配 c 馏慨，匹配到了 c 匹配結(jié)束。

5 動(dòng)態(tài)規(guī)劃

5.1 算法策略

動(dòng)態(tài)規(guī)劃也是將復(fù)雜問(wèn)題分解成小問(wèn)題求解的策略姑隅，與分治算法不同的是写隶，分治算法要求各子問(wèn)題是相互獨(dú)立的，而動(dòng)態(tài)規(guī)劃各子問(wèn)題是相互關(guān)聯(lián)的讲仰。

所以慕趴，動(dòng)態(tài)規(guī)劃適用于子問(wèn)題重疊的情況，即不同的子問(wèn)題具有公共的子子問(wèn)題鄙陡，在這種情況下冕房，分治策略會(huì)做出很多不必要的工作，它會(huì)反復(fù)求解那些公共子子問(wèn)題趁矾，而動(dòng)態(tài)規(guī)劃會(huì)對(duì)每個(gè)子子問(wèn)題求解一次耙册，然后保存在表格中，如果遇到一致的問(wèn)題毫捣，從表格中獲取既可觅玻，所以它無(wú)需求解每一個(gè)子子問(wèn)題，避免了大量的不必要操作培漏。

5.2 適用場(chǎng)景

動(dòng)態(tài)規(guī)劃適用于求解最優(yōu)解問(wèn)題溪厘，比如，從面額不定的100個(gè)硬幣中任意選取多個(gè)湊成10元牌柄，求怎樣選取硬幣才可以使最后選取的硬幣數(shù)最少又剛好湊夠了10元畸悬。這就是一個(gè)典型的動(dòng)態(tài)規(guī)劃問(wèn)題。它可以分成一個(gè)個(gè)子問(wèn)題（每次選取硬幣）珊佣，每個(gè)子問(wèn)題又有公共的子子問(wèn)題（選取硬幣）蹋宦，子問(wèn)題之間相互關(guān)聯(lián)（已選取的硬幣總金額不能超過(guò)10元），邊界條件就是最終選取的硬幣總金額為 10 元咒锻。

針對(duì)上例冷冗，也許你也可以說(shuō)，我們可以使用回溯算法惑艇，不斷的去試探蒿辙，但回溯算法是使用與求解廣度的解（滿足要求的解）拇泛，如果是用回溯算法，我們需要嘗試去找所有滿足條件的解思灌，然后找到最優(yōu)解俺叭，時(shí)間復(fù)雜度為 O(2ⁿ) ，這性能是相當(dāng)差的泰偿。大多數(shù)適用于動(dòng)態(tài)規(guī)劃的問(wèn)題熄守，都可以使用回溯算法，只是使用回溯算法的時(shí)間復(fù)雜度比較高而已耗跛。

最后裕照，總結(jié)一下，我們使用動(dòng)態(tài)規(guī)劃求解問(wèn)題時(shí)调塌，需要遵循以下幾個(gè)重要步驟：

• 定義子問(wèn)題
• 實(shí)現(xiàn)需要反復(fù)執(zhí)行解決的子子問(wèn)題部分
• 識(shí)別并求解出邊界條件

5.3 使用動(dòng)態(tài)規(guī)劃求解的一些經(jīng)典問(wèn)題

• 爬樓梯問(wèn)題：假設(shè)你正在爬樓梯晋南。需要 n 階你才能到達(dá)樓頂。每次你可以爬 1 或 2 個(gè)臺(tái)階烟阐。你有多少種不同的方法可以爬到樓頂呢搬俊？
• 背包問(wèn)題：給出一些資源（有總量及價(jià)值），給一個(gè)背包（有總?cè)萘浚┭亚眩嘲镅b資源琅拌，目標(biāo)是在背包不超過(guò)總?cè)萘康那闆r下浪默，裝入更多的價(jià)值
• 硬幣找零：給出面額不定的一定數(shù)量的零錢(qián)，以及需要找零的錢(qián)數(shù)，找出有多少種找零方案
• 圖的全源最短路徑：一個(gè)圖中包含 u圣贸、v 頂點(diǎn)昭娩，找出從頂點(diǎn) u 到頂點(diǎn) v 的最短路徑
• 最長(zhǎng)公共子序列：找出一組序列的最長(zhǎng)公共子序列（可由另一序列刪除元素但不改變剩下元素的順序?qū)崿F(xiàn)）

這里以最長(zhǎng)公共子序列為例咧欣。

爬樓梯問(wèn)題

這里以動(dòng)態(tài)規(guī)劃經(jīng)典問(wèn)題爬樓梯問(wèn)題為例臭墨，介紹求解動(dòng)態(tài)規(guī)劃問(wèn)題的步驟。

第一步：定義子問(wèn)題

如果用 dp[n] 表示第 n 級(jí)臺(tái)階的方案數(shù)润讥，并且由題目知：最后一步可能邁 2 個(gè)臺(tái)階转锈，也可邁 1 個(gè)臺(tái)階，即第 n 級(jí)臺(tái)階的方案數(shù)等于第 n-1 級(jí)臺(tái)階的方案數(shù)加上第 n-2 級(jí)臺(tái)階的方案數(shù)

第二步：實(shí)現(xiàn)需要反復(fù)執(zhí)行解決的子子問(wèn)題部分

dp[n] = dp[n?1] + dp[n?2]

第三步：識(shí)別并求解出邊界條件

// 第 0 級(jí) 1 種方案 
dp[0]=1 
// 第 1 級(jí)也是 1 種方案 
dp[1]=1

最后一步：把尾碼翻譯成代碼楚殿，處理一些邊界情況

let climbStairs = function(n) {
    let dp = [1, 1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

優(yōu)化空間復(fù)雜度：

let climbStairs = function(n) {
    let res = 1, n1 = 1, n2 = 1
    for(let i = 2; i <= n; i++) {
        res = n1 + n2
        n1 = n2
        n2 = res
    }
    return res
}

空間復(fù)雜度：O(1)

6 枚舉算法

6.1 算法策略

枚舉算法的思想是：將問(wèn)題的所有可能的答案一一列舉撮慨，然后根據(jù)條件判斷此答案是否合適，保留合適的脆粥，丟棄不合適的砌溺。

6.2 解題思路

• 確定枚舉對(duì)象、枚舉范圍和判定條件变隔。
• 逐一列舉可能的解规伐，驗(yàn)證每個(gè)解是否是問(wèn)題的解。

7 刷題

7.1 爬樓梯問(wèn)題

假設(shè)你正在爬樓梯匣缘。需要 n 階你才能到達(dá)樓頂猖闪。

每次你可以爬 1 或 2 個(gè)臺(tái)階鲜棠。你有多少種不同的方法可以爬到樓頂呢？

注意： 給定 n 是一個(gè)正整數(shù)萧朝。

示例 1：

輸入： 2
輸出： 2
解釋?zhuān)?有兩種方法可以爬到樓頂岔留。
1\. 1 階 + 1 階
2\. 2 階

示例 2：

輸入： 3
輸出： 3
解釋?zhuān)?有三種方法可以爬到樓頂夏哭。
1\. 1 階 + 1 階 + 1 階
2\. 1 階 + 2 階
3\. 2 階 + 1 階

解法：動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃（Dynamic Programming检柬，DP）是一種將復(fù)雜問(wèn)題分解成小問(wèn)題求解的策略，但與分治算法不同的是竖配，分治算法要求各子問(wèn)題是相互獨(dú)立的何址，而動(dòng)態(tài)規(guī)劃各子問(wèn)題是相互關(guān)聯(lián)的。

分治进胯，顧名思義用爪，就是分而治之，將一個(gè)復(fù)雜的問(wèn)題胁镐，分成兩個(gè)或多個(gè)相似的子問(wèn)題偎血，在把子問(wèn)題分成更小的子問(wèn)題，直到更小的子問(wèn)題可以簡(jiǎn)單求解盯漂，求解子問(wèn)題颇玷，則原問(wèn)題的解則為子問(wèn)題解的合并。

我們使用動(dòng)態(tài)規(guī)劃求解問(wèn)題時(shí)就缆，需要遵循以下幾個(gè)重要步驟：

• 定義子問(wèn)題
• 實(shí)現(xiàn)需要反復(fù)執(zhí)行解決的子子問(wèn)題部分
• 識(shí)別并求解出邊界條件

第一步：定義子問(wèn)題

如果用 dp[n] 表示第 n 級(jí)臺(tái)階的方案數(shù)帖渠，并且由題目知：最后一步可能邁 2 個(gè)臺(tái)階，也可邁 1 個(gè)臺(tái)階竭宰，即第 n 級(jí)臺(tái)階的方案數(shù)等于第 n-1 級(jí)臺(tái)階的方案數(shù)加上第 n-2 級(jí)臺(tái)階的方案數(shù)

第二步：實(shí)現(xiàn)需要反復(fù)執(zhí)行解決的子子問(wèn)題部分

dp[n] = dp[n?1] + dp[n?2]

第三步：識(shí)別并求解出邊界條件

// 第 0 級(jí) 1 種方案 
dp[0]=1 
// 第 1 級(jí)也是 1 種方案 
dp[1]=1

最后一步：把尾碼翻譯成代碼空郊，處理一些邊界情況

let climbStairs = function(n) {
    let dp = [1, 1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

優(yōu)化空間復(fù)雜度：

let climbStairs = function(n) {
    let res = 1, n1 = 1, n2 = 1
    for(let i = 2; i <= n; i++) {
        res = n1 + n2
        n1 = n2
        n2 = res
    }
    return res
}

空間復(fù)雜度：O(1)

更多解答

7.2 使用最小花費(fèi)爬樓梯

數(shù)組的每個(gè)索引作為一個(gè)階梯，第 i 個(gè)階梯對(duì)應(yīng)著一個(gè)非負(fù)數(shù)的體力花費(fèi)值 cost[i] (索引從0開(kāi)始)切揭。

每當(dāng)你爬上一個(gè)階梯你都要花費(fèi)對(duì)應(yīng)的體力花費(fèi)值狞甚，然后你可以選擇繼續(xù)爬一個(gè)階梯或者爬兩個(gè)階梯。

您需要找到達(dá)到樓層頂部的最低花費(fèi)廓旬。在開(kāi)始時(shí)哼审，你可以選擇從索引為 0 或 1 的元素作為初始階梯。

示例 1:

輸入: cost = [10, 15, 20]
輸出: 15
解釋: 最低花費(fèi)是從cost[1]開(kāi)始嗤谚，然后走兩步即可到階梯頂棺蛛，一共花費(fèi)15。

示例 2:

輸入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
輸出: 6
解釋: 最低花費(fèi)方式是從cost[0]開(kāi)始巩步，逐個(gè)經(jīng)過(guò)那些1旁赊，跳過(guò)cost[3]，一共花費(fèi)6椅野。

注意：

• cost 的長(zhǎng)度將會(huì)在 [2, 1000] 终畅。
• 每一個(gè) cost[i] 將會(huì)是一個(gè)Integer類(lèi)型籍胯，范圍為 [0, 999] 。

解法：動(dòng)態(tài)規(guī)劃

本題注意理解題意：

• 第 i 級(jí)臺(tái)階是第 i-1 級(jí)臺(tái)階的階梯頂部离福。
• 踏上第 i 級(jí)臺(tái)階花費(fèi) cost[i] 杖狼，直接邁一大步跨過(guò)而不踏上去則不用花費(fèi)。
• 樓梯頂部在數(shù)組之外妖爷，如果數(shù)組長(zhǎng)度為 len蝶涩，那么樓頂就在下標(biāo)為 len

第一步：定義子問(wèn)題

踏上第 i 級(jí)臺(tái)階的體力消耗為到達(dá)前兩個(gè)階梯的最小體力消耗加上本層體力消耗：

• 最后邁 1 步踏上第 i 級(jí)臺(tái)階：dp[i-1] + cost[i]
• 最后邁 1 步踏上第 i 級(jí)臺(tái)階：dp[i-2] + cost[i]

第二步：實(shí)現(xiàn)需要反復(fù)執(zhí)行解決的子子問(wèn)題部分

所以踏上第 i 級(jí)臺(tái)階的最小花費(fèi)為：

dp[i] = min(dp[i-2], dp[i-1]) + cost[i]

第三步：識(shí)別并求解出邊界條件

// 第 0 級(jí) cost[0] 種方案 
dp[0] = cost[0]
// 第 1 級(jí)，有兩種情況
// 1：分別踏上第0級(jí)與第1級(jí)臺(tái)階絮识，花費(fèi)cost[0] + cost[1]
// 2：直接從地面開(kāi)始邁兩步直接踏上第1級(jí)臺(tái)階绿聘，花費(fèi)cost[1]
dp[1] = min(cost[0] + cost[1], cost[1]) = cost[1]

最后一步：把尾碼翻譯成代碼，處理一些邊界情況

let minCostClimbingStairs = function(cost) {
    cost.push(0)
    let dp = [], n = cost.length
    dp[0] = cost[0]
    dp[1] = cost[1]
    for(let i = 2; i < n; i++){
        dp[i] = Math.min(dp[i-2] , dp[i-1]) + cost[i]
    }
    return dp[n-1]
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

優(yōu)化：

let minCostClimbingStairs = function(cost) {
    let n = cost.length,
        n1 = cost[0],
        n2 = cost[1] 
    for(let i = 2;i < n;i++){
        let tmp = n2
        n2 = Math.min(n1,n2)+cost[i]
        n1 = tmp
    }
    return Math.min(n1,n2)
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

更多解答

7.3 最大子序和

給定一個(gè)整數(shù)數(shù)組 nums 次舌，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）熄攘，返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大彼念，為 6挪圾。

進(jìn)階:

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解逐沙。

第一步：定義子問(wèn)題

動(dòng)態(tài)規(guī)劃是將整個(gè)數(shù)組歸納考慮哲思，假設(shè)我們已經(jīng)知道了以第 i-1 個(gè)數(shù)結(jié)尾的連續(xù)子數(shù)組的最大和 dp[i-1]，顯然以第i個(gè)數(shù)結(jié)尾的連續(xù)子數(shù)組的最大和的可能取值要么為 dp[i-1]+nums[i]酱吝，要么就是 nums[i] 單獨(dú)成一組也殖，也就是 nums[i] ，在這兩個(gè)數(shù)中我們?nèi)∽畲笾?/p>

第二步：實(shí)現(xiàn)需要反復(fù)執(zhí)行解決的子子問(wèn)題部分

dp[n] = Math.max(dp[n?1]+nums[n], nums[n])

第三步：識(shí)別并求解出邊界條件

dp[0]=nums[0]

最后一步：把尾碼翻譯成代碼务热，處理一些邊界情況

因?yàn)槲覀冊(cè)谟?jì)算 dp[i] 的時(shí)候忆嗜，只關(guān)心 dp[i-1] 與 nums[i]，因此不用把整個(gè) dp 數(shù)組保存下來(lái)崎岂，只需設(shè)置一個(gè) pre 保存 dp[i-1] 就好了捆毫。

代碼實(shí)現(xiàn)（優(yōu)化）：

let maxSubArray = function(nums) {
    let max = nums[0], pre = 0
    for(const num of nums) {
        if(pre > 0) {
            pre += num
        } else {
            pre = num
        }
        max = Math.max(max, pre)
    }
    return max
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

更多解答

7.4 買(mǎi)賣(mài)股票的最佳時(shí)機(jī)

給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格冲甘。

如果你最多只允許完成一筆交易（即買(mǎi)入和賣(mài)出一支股票一次）绩卤，設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。

注意：你不能在買(mǎi)入股票前賣(mài)出股票江醇。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入濒憋，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出，最大利潤(rùn) = 6-1 = 5 陶夜。
     注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u(mài)出價(jià)格需要大于買(mǎi)入價(jià)格凛驮；同時(shí)，你不能在買(mǎi)入前賣(mài)出股票条辟。

示例 2:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0黔夭。

解法：動(dòng)態(tài)規(guī)劃

第一步：定義子問(wèn)題

動(dòng)態(tài)規(guī)劃是將整個(gè)數(shù)組歸納考慮宏胯，假設(shè)我們已經(jīng)知道了 i-1 個(gè)股票的最大利潤(rùn)為 dp[i-1]，顯然 i 個(gè)連續(xù)股票的最大利潤(rùn)為 dp[i-1] 本姥，要么就是就是 prices[i] - minprice （ minprice 為前 i-1 支股票的最小值 ）肩袍，在這兩個(gè)數(shù)中我們?nèi)∽畲笾?/p>

第二步：實(shí)現(xiàn)需要反復(fù)執(zhí)行解決的子子問(wèn)題部分

dp[i] = Math.max(dp[i?1], prices[i] - minprice)

第三步：識(shí)別并求解出邊界條件

dp[0]=0

最后一步：把尾碼翻譯成代碼，處理一些邊界情況

因?yàn)槲覀冊(cè)谟?jì)算 dp[i] 的時(shí)候婚惫，只關(guān)心 dp[i-1] 與 prices[i]氛赐，因此不用把整個(gè) dp 數(shù)組保存下來(lái)，只需設(shè)置一個(gè) max 保存 dp[i-1] 就好了辰妙。

代碼實(shí)現(xiàn)（優(yōu)化）：

let maxProfit = function(prices) {
    let max = 0, minprice = prices[0]
    for(let i = 1; i < prices.length; i++) {
        minprice = Math.min(prices[i], minprice)
        max = Math.max(max, prices[i] - minprice)
    }
    return max
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

更多解答

7.5 回文子串

給定一個(gè)字符串鹰祸，你的任務(wù)是計(jì)算這個(gè)字符串中有多少個(gè)回文子串甫窟。

具有不同開(kāi)始位置或結(jié)束位置的子串密浑，即使是由相同的字符組成，也會(huì)被視作不同的子串粗井。

示例 1：

輸入："abc"
輸出：3
解釋?zhuān)喝齻€(gè)回文子串: "a", "b", "c"

示例 2：

輸入："aaa"
輸出：6
解釋?zhuān)?個(gè)回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

• 輸入的字符串長(zhǎng)度不會(huì)超過(guò) 1000 尔破。

解法一：暴力法

let countSubstrings = function(s) {
  let count = 0
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (isPalindrome(s.substring(i, j + 1))) {
        count++
      }
    }
  }
  return count
}

let isPalindrome = function(s) {
  let i = 0, j = s.length - 1
  while (i < j) {
    if (s[i] != s[j]) return false
    i++
    j--
  }
  return true
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n³)
• 空間復(fù)雜度：O(1)

解法二：動(dòng)態(tài)規(guī)劃

一個(gè)字符串是回文串，它的首尾字符相同浇衬，且剩余子串也是一個(gè)回文串懒构。其中，剩余子串是否為回文串耘擂，就是規(guī)模小一點(diǎn)的子問(wèn)題胆剧，它的結(jié)果影響大問(wèn)題的結(jié)果。

我們?cè)趺慈ッ枋鲎訂?wèn)題呢醉冤？

顯然秩霍，一個(gè)子串由兩端的 i 、j 指針確定蚁阳，就是描述子問(wèn)題的變量铃绒，子串 s[i...j] （ dp[i][j] ） 是否是回文串，就是子問(wèn)題螺捐。

我們用二維數(shù)組記錄計(jì)算過(guò)的子問(wèn)題的結(jié)果颠悬，從base case出發(fā)，像填表一樣遞推出每個(gè)子問(wèn)題的解定血。

    j
    a  a  b  a
i a ?
  a    ?  
  b       ?
  a          ?

注意： i<=j 赔癌，只需用半張表，豎向掃描

所以：

i === j：dp[i][j]=true
j - i == 1 && s[i] == s[j]：dp[i][j] = true
j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]：dp[i][j] = true

即：

s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]): dp[i][j]=true

否則為 false

代碼實(shí)現(xiàn)：

let countSubstrings = function(s) {
  const len = s.length
  let count = 0
  const dp = new Array(len)

  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(false)
  }
  for (let j = 0; j < len; j++) {
    for (let i = 0; i <= j; i++) {
      if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
        dp[i][j] = true
        count++
      } else {
        dp[i][j] = false
      }
    }
  }
  return count
}

代碼實(shí)現(xiàn)（優(yōu)化）：

把上圖的表格豎向一列看作一維數(shù)組澜沟，還是豎向掃描灾票，此時(shí)僅僅需要將 dp 定義為一維數(shù)組即可

let countSubstrings = function(s) {
  const len = s.length
  let count = 0
  const dp = new Array(len)

  for (let j = 0; j < len; j++) {
    for (let i = 0; i <= j; i++) {
      if (s[i] === s[j] && (j - i <= 1 || dp[i + 1])) {
        dp[i] = true
        count++
      } else {
        dp[i] = false
      }
    }
  }
  return count;
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n²)
• 空間復(fù)雜度：O(n)

更多解答

7.6 最長(zhǎng)回文子串

給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串倔喂。你可以假設(shè) s 的最大長(zhǎng)度為 1000铝条。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案靖苇。

示例 2：

輸入: "cbbd"
輸出: "bb"

解法：動(dòng)態(tài)規(guī)劃

第 1 步：定義狀態(tài)

dp[i][j] 表示子串 s[i..j] 是否為回文子串，這里子串 s[i..j] 定義為左閉右閉區(qū)間班缰，可以取到 s[i] 和 s[j] 贤壁。

第 2 步：思考狀態(tài)轉(zhuǎn)移方程

對(duì)于一個(gè)子串而言，如果它是回文串埠忘，那么在它的首尾增加一個(gè)相同字符脾拆，它仍然是個(gè)回文串

dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1]

第 3 步：初始狀態(tài)：

dp[i][i] = true // 單個(gè)字符是回文串
if(s[i] === s[i+1]) dp[i][i+1] = true // 連續(xù)兩個(gè)相同字符是回文串 

代碼實(shí)現(xiàn)：

const longestPalindrome = (s) => {
  if (s.length < 2) return s
  // res: 最長(zhǎng)回文子串
  let res = s[0], dp = []
  for (let i = 0; i < s.length; i++) {
    dp[i][i] = true
  }
  for (let j = 1; j < s.length; j++) {
    for (let i = 0; i < j; i++) {
      if (j - i === 1 && s[i] === s[j]) {
        dp[i][j] = true
      } else if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true
      }   
      // 獲取當(dāng)前最長(zhǎng)回文子串
      if (dp[i][j] && j - i + 1 > res.length) {
        res = s.substring(i, j + 1)
      }
    }
  }

  return res
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n²)
• 空間復(fù)雜度：O(n²)

更多解答

7.7 最小路徑和

給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請(qǐng)找出一條從左上角到右下角的路徑莹妒，使得路徑上的數(shù)字總和為最小名船。

說(shuō)明：每次只能向下或者向右移動(dòng)一步。

aee3c3fad27b04ac514fcc06fe2bf264_v2-fb7754ca71f70bc1631b02a29677221a_r.jpg

示例 1：

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋?zhuān)阂驗(yàn)槁窂?1→3→1→1→1 的總和最小旨怠。

示例 2：

輸入：grid = [[1,2,3],[4,5,6]]
輸出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

1渠驼、DP方程 當(dāng)前項(xiàng)最小路徑和 = 當(dāng)前項(xiàng)值 + 上項(xiàng)或左項(xiàng)中的最小值 grid[i][j] += Math.min( grid[i - 1][j], grid[i][j - 1] )

2、邊界處理 grid的第一行與第一列 分別沒(méi)有上項(xiàng)與左項(xiàng) 故單獨(dú)處理計(jì)算起項(xiàng)最小路徑和 計(jì)算第一行：

for(let j = 1; j < col; j++) grid[0][j] += grid[0][j - 1]

計(jì)算第一列：

for(let i = 1; i < row; i++) grid[i][0] += grid[i - 1][0]

3鉴腻、代碼實(shí)現(xiàn)

var minPathSum = function(grid) {
    let row = grid.length, col = grid[0].length

    // calc boundary
    for(let i = 1; i < row; i++)
        // calc first col
        grid[i][0] += grid[i - 1][0]

    for(let j = 1; j < col; j++)
        // calc first row
        grid[0][j] += grid[0][j - 1]

    for(let i = 1; i < row; i++)
        for(let j = 1; j < col; j++)
            grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])

    return grid[row - 1][col - 1]
};

更多解答

7.8 買(mǎi)賣(mài)股票的最佳時(shí)機(jī) II

給定一個(gè)數(shù)組迷扇，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。

設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)爽哎。你可以盡可能地完成更多的交易（多次買(mǎi)賣(mài)一支股票）蜓席。

注意： 你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入课锌，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 厨内。
     隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買(mǎi)入渺贤，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 6-3 = 3 雏胃。

示例 2:

輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 癣亚。
     注意你不能在第 1 天和第 2 天接連購(gòu)買(mǎi)股票丑掺，之后再將它們賣(mài)出。
     因?yàn)檫@樣屬于同時(shí)參與了多筆交易述雾，你必須在再次購(gòu)買(mǎi)前出售掉之前的股票街州。

示例 3:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。

提示：

• 1 <= prices.length <= 3 * 10 ^ 4
• 0 <= prices[i] <= 10 ^ 4

解法一：峰底買(mǎi)入玻孟，峰頂賣(mài)出

5679aaf9ae5f2b6292ece496e3e01acb_v2-d88340f20c1d2183ece942637b6cede8_r.jpg

如圖唆缴，在第二天買(mǎi)入，第三天賣(mài)出黍翎，第四天買(mǎi)入面徽，第五天賣(mài)出獲利最高，此處代碼不再贅述，可以自己嘗試寫(xiě)一下

解法二：貪心算法

貪心算法趟紊，故名思義氮双，總是做出當(dāng)前的最優(yōu)選擇，即期望通過(guò)局部的最優(yōu)選擇獲得整體的最優(yōu)選擇霎匈。

某種意義上說(shuō)戴差，貪心算法是很貪婪、很目光短淺的铛嘱，它不從整體考慮暖释，僅僅只關(guān)注當(dāng)前的最大利益，所以說(shuō)它做出的選擇僅僅是某種意義上的局部最優(yōu)墨吓，但是貪心算法在很多問(wèn)題上還是能夠拿到最優(yōu)解或較優(yōu)解球匕，所以它的存在還是有意義的。

對(duì)應(yīng)于該題帖烘，第一天買(mǎi)入亮曹，第二天賣(mài)出，…蚓让，第 i 天買(mǎi)入乾忱，第 i+1 天賣(mài)出，如果 i 天買(mǎi)入第 i+1 天賣(mài)出有利潤(rùn)則買(mǎi)入历极，否則不買(mǎi)

第 i-1 天買(mǎi)入第 i 天賣(mài)出獲利 prices[i+1]-prices[i] ，我們僅僅需要將 prices[i+1]-prices[i] 的所有正值加起來(lái)就是可獲取的最大利益

代碼實(shí)現(xiàn)：

let maxProfit = function(prices) {
    let profit = 0
    for (let i = 0; i < prices.length - 1; i++) {
        if (prices[i + 1] > prices[i]) {
            profit += prices[i + 1] - prices[i]
        }
    }
    return profit
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

更多解答

7.9 分發(fā)餅干

假設(shè)你是一位很棒的家長(zhǎng)衷佃，想要給你的孩子們一些小餅干趟卸。但是，每個(gè)孩子最多只能給一塊餅干氏义。對(duì)每個(gè)孩子 i 锄列，都有一個(gè)胃口值 g_i ，這是能讓孩子們滿足胃口的餅干的最小尺寸惯悠；并且每塊餅干 j 邻邮，都有一個(gè)尺寸 s_j。如果 s_j >= g_i 克婶，我們可以將這個(gè)餅干 j 分配給孩子 i 筒严，這個(gè)孩子會(huì)得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子情萤，并輸出這個(gè)最大數(shù)值鸭蛙。

注意：

你可以假設(shè)胃口值為正。一個(gè)小朋友最多只能擁有一塊餅干筋岛。

示例 1:

輸入: [1,2,3], [1,1]

輸出: 1

解釋: 
你有三個(gè)孩子和兩塊小餅干娶视，3個(gè)孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1肪获，你只能讓胃口值是1的孩子滿足寝凌。
所以你應(yīng)該輸出1。

示例 2:

輸入: [1,2], [1,2,3]

輸出: 2

解釋: 
你有兩個(gè)孩子和三塊小餅干孝赫，2個(gè)孩子的胃口值分別是1,2硫兰。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應(yīng)該輸出2.

解法：貪心算法

const findContentChildren = (g, s) => {
    if (!g.length || !s.length) return 0

    g.sort((a, b) => a - b)
    s.sort((a, b) => a - b)

    let gi = 0, si = 0
    while (gi < g.length && si < s.length) {
        if (g[gi] <= s[si++]) gi++
    }
    return gi
}

更多解答

7.10 分割數(shù)組為連續(xù)子序列

給你一個(gè)按升序排序的整數(shù)數(shù)組 num（可能包含重復(fù)數(shù)字）寒锚，請(qǐng)你將它們分割成一個(gè)或多個(gè)子序列劫映，其中每個(gè)子序列都由連續(xù)整數(shù)組成且長(zhǎng)度至少為 3 。

如果可以完成上述分割刹前，則返回 true 泳赋；否則，返回 false 喇喉。

示例 1：

輸入: [1,2,3,3,4,5]
輸出: True
解釋:
你可以分割出這樣兩個(gè)連續(xù)子序列 : 
1, 2, 3
3, 4, 5

示例 2：

輸入: [1,2,3,3,4,4,5,5]
輸出: True
解釋:
你可以分割出這樣兩個(gè)連續(xù)子序列 : 
1, 2, 3, 4, 5
3, 4, 5

示例 3：

輸入: [1,2,3,4,4,5]
輸出: False

提示：

• 輸入的數(shù)組長(zhǎng)度范圍為 [1, 10000]

解法：貪心算法

從頭開(kāi)始祖今，我們每次僅僅尋找滿足條件的序列（連續(xù)子序列長(zhǎng)度為3），剔除之后拣技，依次往后遍歷：

• 判斷當(dāng)前元素是否能夠拼接到前一個(gè)滿足條件的連續(xù)子序列上千诬，可以的話，則拼接
• 如果不可以膏斤，則判斷以當(dāng)前元素開(kāi)始能否構(gòu)成連續(xù)子序列（長(zhǎng)度為3）徐绑，可以的話，則剔除連續(xù)子序列
• 否則莫辨，返回 false

const isPossible = function(nums) {
    let max = nums[nums.length - 1]
    // arr：存儲(chǔ)原數(shù)組中數(shù)字每個(gè)數(shù)字出現(xiàn)的次數(shù)
    // tail：存儲(chǔ)以數(shù)字num結(jié)尾的且符合題意的連續(xù)子序列個(gè)數(shù)
    let arr = new Array(max + 2).fill(0), 
        tail = new Array(max + 2).fill(0)
    for(let num of nums) {
        arr[num] ++
    }
    for(let num of nums) {
        if(arr[num] === 0) continue
        else if(tail[num-1] > 0){
            tail[num-1]--
            tail[num]++
        }else if(arr[num+1] > 0 && arr[num+2] > 0){
            arr[num+1]--
            arr[num+2]--
            tail[num+2]++
        } else {
            return false
        }
        arr[num]--
    }
    return true
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

更多解答

7.11 全排列問(wèn)題

給定一個(gè) 沒(méi)有重復(fù) 數(shù)字的序列傲茄，返回其所有可能的全排列。

示例:

輸入: [1,2,3]
輸出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解法：回溯算法

本題是回溯算法的經(jīng)典應(yīng)用場(chǎng)景

1. 算法策略

回溯算法是一種搜索法沮榜，試探法盘榨，它會(huì)在每一步做出選擇，一旦發(fā)現(xiàn)這個(gè)選擇無(wú)法得到期望結(jié)果蟆融，就回溯回去草巡，重新做出選擇。深度優(yōu)先搜索利用的就是回溯算法思想型酥。

2. 適用場(chǎng)景

回溯算法很簡(jiǎn)單山憨，它就是不斷的嘗試，直到拿到解冕末。它的這種算法思想萍歉，使它通常用于解決廣度的搜索問(wèn)題，即從一組可能的解中档桃，選擇一個(gè)滿足要求的解枪孩。

3. 代碼實(shí)現(xiàn)

我們可以寫(xiě)一下，數(shù)組 [1, 2, 3] 的全排列有：

• 先寫(xiě)以 1 開(kāi)頭的全排列，它們是：[1, 2, 3], [1, 3, 2]蔑舞，即 1 + [2, 3] 的全排列拒担；
• 再寫(xiě)以 2 開(kāi)頭的全排列，它們是：[2, 1, 3], [2, 3, 1]攻询，即 2 + [1, 3] 的全排列从撼；
• 最后寫(xiě)以 3 開(kāi)頭的全排列，它們是：[3, 1, 2], [3, 2, 1]钧栖，即 3 + [1, 2] 的全排列低零。

即回溯的處理思想，有點(diǎn)類(lèi)似枚舉搜索拯杠。我們枚舉所有的解掏婶，找到滿足期望的解。為了有規(guī)律地枚舉所有可能的解潭陪，避免遺漏和重復(fù)雄妥，我們把問(wèn)題求解的過(guò)程分為多個(gè)階段。每個(gè)階段依溯，我們都會(huì)面對(duì)一個(gè)岔路口老厌，我們先隨意選一條路走，當(dāng)發(fā)現(xiàn)這條路走不通的時(shí)候（不符合期望的解）黎炉，就回退到上一個(gè)岔路口枝秤，另選一種走法繼續(xù)走。

這顯然是一個(gè) 遞歸 結(jié)構(gòu)拜隧；

• 遞歸的終止條件是：一個(gè)排列中的數(shù)字已經(jīng)選夠了 宿百，因此我們需要一個(gè)變量來(lái)表示當(dāng)前程序遞歸到第幾層，我們把這個(gè)變量叫做 depth 洪添，或者命名為 index ，表示當(dāng)前要確定的是某個(gè)全排列中下標(biāo)為 index 的那個(gè)數(shù)是多少雀费；
• used（object）：用于把表示一個(gè)數(shù)是否被選中干奢，如果這個(gè)數(shù)字(num)被選擇這設(shè)置為 used[num] = true ，這樣在考慮下一個(gè)位置的時(shí)候盏袄，就能夠以 O(1)的時(shí)間復(fù)雜度判斷這個(gè)數(shù)是否被選擇過(guò)忿峻，這是一種「以空間換時(shí)間」的思想。

let permute = function(nums) {
    // 使用一個(gè)數(shù)組保存所有可能的全排列
    let res = []
    if (nums.length === 0) {
        return res
    }
    let used = {}, path = []
    dfs(nums, nums.length, 0, path, used, res)
    return res
}
let dfs = function(nums, len, depth, path, used, res) {
    // 所有數(shù)都填完了
    if (depth === len) {
        res.push([...path])
        return
    }
    for (let i = 0; i < len; i++) {
        if (!used[i]) {
            // 動(dòng)態(tài)維護(hù)數(shù)組
            path.push(nums[i])
            used[i] = true
            // 繼續(xù)遞歸填下一個(gè)數(shù)
            dfs(nums, len, depth + 1, path, used, res)
            // 撤銷(xiāo)操作
            used[i] = false
            path.pop()
        }

    }
}

4. 復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n?n!)辕羽，其中 n 為序列的長(zhǎng)度這是一個(gè)排列組合逛尚，每層的排列組合數(shù)為：A^m _n=n!/(n?m)! ，故而所有的排列有 ：A¹ _n + A² _n + … + A^n-1 _n = n!/(n?1)! + n!/(n?2)! + … + n! = n! * (1/(n?1)! + 1/(n?2)! + … + 1) <= n! * (1 + 1/2 + 1/4 + … + 1/2^n-1) < 2 * n!并且每個(gè)內(nèi)部結(jié)點(diǎn)循環(huán) n 次刁愿，故非葉子結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(n?n!)
• 空間復(fù)雜度：O(n)

更多解答

7.12 括號(hào)生成

數(shù)字 n 代表生成括號(hào)的對(duì)數(shù)绰寞，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)，用于能夠生成所有可能的并且 有效的 括號(hào)組合。

示例：

輸入：n = 3
輸出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

解答：回溯算法（深度優(yōu)先遍歷）

算法策略： 回溯算法是一種搜索法滤钱，試探法觉壶，它會(huì)在每一步做出選擇，一旦發(fā)現(xiàn)這個(gè)選擇無(wú)法得到期望結(jié)果件缸，就回溯回去铜靶，重新做出選擇。深度優(yōu)先搜索利用的就是回溯算法思想他炊。

對(duì)應(yīng)于本題争剿，我們可以每次試探增加 ( 或 ) ，注意：

• 加入 ( 的條件是痊末，當(dāng)前是否還有 ( 可以選擇
• 加入 ) 的時(shí)候蚕苇，受到 ( 的限制，如果已選擇的結(jié)果里的 ( 小于等于已選擇里的 ) 時(shí)舌胶，此時(shí)是不能選擇 ) 的捆蜀，例如如果當(dāng)前是 () ，繼續(xù)選擇 ) 就是 ()) 幔嫂，是不合法的

代碼實(shí)現(xiàn)：

const generateParenthesis = (n) => {
    const res = []
    const dfs = (path, left, right) => {
        // 肯定不合法辆它，提前結(jié)束
        if (left > n || left < right) return
        // 到達(dá)結(jié)束條件
        if (left + right === 2 * n) {
            res.push(path)
            return
        }
        // 選擇
        dfs(path + '(', left + 1, right)
        dfs(path + ')', left, right + 1)
    }
    dfs('', 0, 0)
    return res
}

復(fù)雜度分析（來(lái)源leetcode官方題解）：

698ffc5bed3ecdc545fddfa3d21d8f21_v2-1bba9f0758bfd41e62a6dd07b65ef3a5_r.jpg