參考引用

• Hello 算法
• Github：hello-algo

1. 動(dòng)態(tài)規(guī)劃算法

• 動(dòng)態(tài)規(guī)劃將一個(gè)問(wèn)題分解為一系列更小的子問(wèn)題，并通過(guò)存儲(chǔ)子問(wèn)題的解來(lái)避免重復(fù)計(jì)算，從而大幅提升時(shí)間效率

問(wèn)題：給定一個(gè)共有 n 階的樓梯，你每步可以上 1 階或者 2 階，請(qǐng)問(wèn)有多少種方案可以爬到樓頂？

• 下圖所示，對(duì)于一個(gè) 3 階樓梯，共有 3 種方案可以爬到樓頂

• 本題的目標(biāo)是求解方案數(shù)量，可以考慮通過(guò)回溯來(lái)窮舉所有可能性。具體來(lái)說(shuō)，將爬樓梯想象為一個(gè)多輪選擇的過(guò)程：從地面出發(fā)，每輪選擇上 1 階或 2 階，每當(dāng)?shù)竭_(dá)樓梯頂部時(shí)就將方案數(shù)量加 1，當(dāng)越過(guò)樓梯頂部時(shí)就將其剪枝

  /* 回溯 */
  void backtrack(vector<int> &choices, int state, int n, vector<int> &res) {// 當(dāng)爬到第 n 階時(shí)，方案數(shù)量加 1if (state == n)res[0]++;// 遍歷所有選擇for (auto &choice : choices) {// 剪枝：不允許越過(guò)第 n 階if (state + choice > n)break;// 嘗試：做出選擇，更新?tīng)顟B(tài)backtrack(choices, state + choice, n, res);// 回退}
  }/* 爬樓梯：回溯 */
  int climbingStairsBacktrack(int n) {vector<int> choices = {1, 2}; // 可選擇向上爬 1 或 2 階int state = 0;                // 從第 0 階開(kāi)始爬vector<int> res = {0};        // 使用 res[0] 記錄方案數(shù)量backtrack(choices, state, n, res);return res[0];
  }
  

1.1 方法一：暴力搜索

• 回溯算法通常并不顯式地對(duì)問(wèn)題進(jìn)行拆解，而是將問(wèn)題看作一系列決策步驟，通過(guò)試探和剪枝，搜索所有可能的解?？梢試L試從問(wèn)題分解的角度分析這道題。設(shè)爬到第 $i$ 階共有 $dp[i]$ 種方案，那么 $dp[i]$ 就是原問(wèn)題，其子問(wèn)題包括

$$dp[i?1],dp[i?2],\dots ,dp[2],dp[1]$$

• 由于每輪只能上 1 階或 2 階，因此當(dāng)站在第 i 階樓梯上時(shí)，上一輪只可能站在第 i-1 階或第 i-2 階上。換句話說(shuō)，只能從第 i-1 階或第 i-2 階前往第 i 階
  • 由此便可得出一個(gè)重要推論：爬到第 i-1 階的方案數(shù)加上爬到第 i-2 階的方案數(shù)就等于爬到第 i 階的方案數(shù)
  • 在爬樓梯問(wèn)題中，各子問(wèn)題之間存在遞推關(guān)系，原問(wèn)題的解可以由子問(wèn)題的解構(gòu)建得來(lái)，下圖展示了該遞推關(guān)系

$$dp[i]=dp[i?1]+dp[i?2]$$

• 可以根據(jù)遞推公式得到暴力搜索解法
  • 以 $dp[n]$ 為起始點(diǎn)，遞歸地將一個(gè)較大問(wèn)題拆解為兩個(gè)較小問(wèn)題的和，直至到達(dá)最小子問(wèn)題 $dp[1]$ 和 $dp[2]$ 時(shí)返回。其中，最小子問(wèn)題的解是已知的，即 $dp[1]=1$、$dp[2]=2$，表示爬到第 1、2 階分別有 1、2 種方案

  /* 搜索 */
  int dfs(int i) {// 已知 dp[1] 和 dp[2] ，返回之if (i == 1 || i == 2)return i;// dp[i] = dp[i-1] + dp[i-2]int count = dfs(i - 1) + dfs(i - 2);return count;
  }/* 爬樓梯：搜索 */
  int climbingStairsDFS(int n) {return dfs(n);
  }
  

• 下圖展示了暴力搜索形成的遞歸樹(shù)。對(duì)于問(wèn)題 $dp[n]$，其遞歸樹(shù)的深度為 n，時(shí)間復(fù)雜度為 $O(2^n)$
  • 指數(shù)階屬于爆炸式增長(zhǎng)，如果輸入一個(gè)比較大的 n，則會(huì)陷入漫長(zhǎng)的等待之中
  • 指數(shù)階的時(shí)間復(fù)雜度是由于 “重疊子問(wèn)題” 導(dǎo)致的，以此類推，子問(wèn)題中包含更小的重疊子問(wèn)題，子子孫孫無(wú)窮盡也，絕大部分計(jì)算資源都浪費(fèi)在這些重疊的問(wèn)題上

1.2 方法二：記憶化搜索

• 為了提升算法效率，希望所有的重疊子問(wèn)題都只被計(jì)算一次。為此，聲明一個(gè)數(shù)組 mem 來(lái)記錄每個(gè)子問(wèn)題的解，并在搜索過(guò)程中將重疊子問(wèn)題剪枝
  • 當(dāng)首次計(jì)算 $dp[i]$ 時(shí)，將其記錄至 mem[i]，以便之后使用
  • 當(dāng)再次需要計(jì)算 $dp[i]$ 時(shí)，便可直接從 mem[i] 中獲取結(jié)果，從而避免重復(fù)計(jì)算該子問(wèn)題

  /* 記憶化搜索 */
  int dfs(int i, vector<int> &mem) {// 已知 dp[1] 和 dp[2] ，返回之if (i == 1 || i == 2)return i;// 若存在記錄 dp[i] ，則直接返回之if (mem[i] != -1)return mem[i];// dp[i] = dp[i-1] + dp[i-2]int count = dfs(i - 1, mem) + dfs(i - 2, mem);// 記錄 dp[i]mem[i] = count;return count;
  }/* 爬樓梯：記憶化搜索 */
  int climbingStairsDFSMem(int n) {// mem[i] 記錄爬到第 i 階的方案總數(shù)，-1 代表無(wú)記錄vector<int> mem(n + 1, -1);return dfs(n, mem);
  }
  

• 下圖所示，經(jīng)過(guò)記憶化處理后，所有重疊子問(wèn)題都只需被計(jì)算一次，時(shí)間復(fù)雜度被優(yōu)化至 O(n)
  • 記憶化搜索是一種 “從頂至底” 的方法，從原問(wèn)題（根節(jié)點(diǎn)）開(kāi)始，遞歸地將較大子問(wèn)題分解為較小子問(wèn)題，直至解已知的最小子問(wèn)題（葉節(jié)點(diǎn)）。之后，通過(guò)回溯將子問(wèn)題的解逐層收集，構(gòu)建出原問(wèn)題的解

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

• 動(dòng)態(tài)規(guī)劃是一種 “從底至頂” 的方法：從最小子問(wèn)題的解開(kāi)始，迭代地構(gòu)建更大子問(wèn)題的解，直至得到原問(wèn)題的解
  • 由于動(dòng)態(tài)規(guī)劃不包含回溯過(guò)程，因此只需使用循環(huán)迭代實(shí)現(xiàn)，無(wú)須使用遞歸。在以下代碼中，初始化一個(gè)數(shù)組 dp 來(lái)存儲(chǔ)子問(wèn)題的解

  /* 爬樓梯：動(dòng)態(tài)規(guī)劃 */
  int climbingStairsDP(int n) {if (n == 1 || n == 2)return n;// 初始化 dp 表，用于存儲(chǔ)子問(wèn)題的解vector<int> dp(n + 1);// 初始狀態(tài)：預(yù)設(shè)最小子問(wèn)題的解dp[1] = 1;dp[2] = 2;// 狀態(tài)轉(zhuǎn)移：從較小子問(wèn)題逐步求解較大子問(wèn)題for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
  }
  

根據(jù)以上內(nèi)容，總結(jié)出動(dòng)態(tài)規(guī)劃的常用術(shù)語(yǔ)

• 將數(shù)組 $dp$ 稱為 $dp$ 表，$dp[i]$ 表示狀態(tài) $i$ 對(duì)應(yīng)子問(wèn)題的解
• 將最小子問(wèn)題對(duì)應(yīng)的狀態(tài)（即第 1 和 2 階樓梯）稱為初始狀態(tài)
• 將遞推公式 $dp[i]=dp[i?1]+dp[i?2]$ 稱為狀態(tài)轉(zhuǎn)移方程

1.4 空間優(yōu)化

• 由于 $dp[i]$ 只與 $dp[i?1]$ 和 $dp[i?2]$ 有關(guān)，因此無(wú)須使用一個(gè)數(shù)組 dp 來(lái)存儲(chǔ)所有子問(wèn)題的解，而只需兩個(gè)變量滾動(dòng)前進(jìn)即可

  /* 爬樓梯：空間優(yōu)化后的動(dòng)態(tài)規(guī)劃 */
  // 空間復(fù)雜度從 O(n) 降低至 O(1)
  int climbingStairsDPComp(int n) {if (n == 1 || n == 2)return n;int a = 1, b = 2;for (int i = 3; i <= n; i++) {int tmp = b;b = a + b;a = tmp;}return b;
  }
  

在動(dòng)態(tài)規(guī)劃問(wèn)題中，當(dāng)前狀態(tài)往往僅與前面有限個(gè)狀態(tài)有關(guān)，這時(shí)可以只保留必要的狀態(tài)，通過(guò) “降維” 來(lái)節(jié)省內(nèi)存空間，這種空間優(yōu)化技巧被稱為 “滾動(dòng)變量” 或 “滾動(dòng)數(shù)組”

2. 貪心算法

• 貪心算法是一種常見(jiàn)的解決優(yōu)化問(wèn)題的算法，其基本思想是：在問(wèn)題的每個(gè)決策階段，都選擇當(dāng)前看起來(lái)最優(yōu)的選擇，即貪心地做出局部最優(yōu)的決策，以期望獲得全局最優(yōu)解

• 貪心算法和動(dòng)態(tài)規(guī)劃都常用于解決優(yōu)化問(wèn)題，它們之間的區(qū)別如下

  • 動(dòng)態(tài)規(guī)劃會(huì)根據(jù)之前階段的所有決策來(lái)考慮當(dāng)前決策，并使用過(guò)去子問(wèn)題的解來(lái)構(gòu)建當(dāng)前子問(wèn)題的解
  • 貪心算法不會(huì)重新考慮過(guò)去的決策，而是一路向前地進(jìn)行貪心選擇，不斷縮小問(wèn)題范圍，直至問(wèn)題被解決

問(wèn)題：給定 n 種硬幣，第 i 種硬幣的面值為 coins[i-1]，目標(biāo)金額為 amt，每種硬幣可以重復(fù)選取，問(wèn)能夠湊出目標(biāo)金額的最少硬幣個(gè)數(shù)，如果無(wú)法湊出目標(biāo)金額則返回 -1

/* 零錢兌換：貪心 */
int coinChangeGreedy(vector<int> &coins, int amt) {// 假設(shè) coins 列表有序int i = coins.size() - 1;int count = 0;// 循環(huán)進(jìn)行貪心選擇，直到無(wú)剩余金額while (amt > 0) {// 找到小于且最接近剩余金額的硬幣while (i > 0 && coins[i] > amt) {i--;}// 選擇 coins[i]amt -= coins[i];count++;}// 若未找到可行方案，則返回 -1return amt == 0 ? count : -1;
}

2.1 貪心算法優(yōu)缺點(diǎn)

• 貪心算法不僅操作直接、實(shí)現(xiàn)簡(jiǎn)單，而且通常效率也很高。在以上代碼中，記硬幣最小面值為 $min(coins)$，則貪心選擇最多循環(huán) $amt/min(coins)$ 次，時(shí)間復(fù)雜度為 $O(amt/min(coins))$。這比動(dòng)態(tài)規(guī)劃解法的時(shí)間復(fù)雜度 $O(n?amt)$ 提升了一個(gè)數(shù)量級(jí)

• 然而，對(duì)于某些硬幣面值組合，貪心算法并不能找到最優(yōu)解

  • 正例 $coins=[1,5,10,20,50,100]$：在該硬幣組合下，給定任意 $amt$，貪心算法都可以找出最優(yōu)解
  • 反例 1 $coins=[1,20,50]$：假設(shè) $amt=60$，貪心算法只能找到 $50+1\times 10$ 的兌換組合，共計(jì) 11 枚硬幣，但動(dòng)態(tài)規(guī)劃可以找到最優(yōu)解 $20+20+20$，僅需 3 枚硬幣
  • 反例 2 $coins=[1,49,50]$：假設(shè) $amt=98$，貪心算法只能找到 $50+1\times 48$ 的兌換組合，共計(jì) 49 枚硬幣，但動(dòng)態(tài)規(guī)劃可以找到最優(yōu)解 $49+49$，僅需 2 枚硬幣

• 一般情況下，貪心算法適用于以下兩類問(wèn)題
  • 可以保證找到最優(yōu)解：貪心算法在這種情況下往往是最優(yōu)選擇，因?yàn)樗然厮荨?dòng)態(tài)規(guī)劃更高效
  • 可以找到近似最優(yōu)解：對(duì)于很多復(fù)雜問(wèn)題來(lái)說(shuō)，尋找全局最優(yōu)解是非常困難的，能以較高效率找到次優(yōu)解也是非常不錯(cuò)的

2.2 貪心典型例題

• 硬幣找零問(wèn)題
  • 在某些硬幣組合下，貪心算法總是可以得到最優(yōu)解
• 區(qū)間調(diào)度問(wèn)題
  • 假設(shè)你有一些任務(wù)，每個(gè)任務(wù)在一段時(shí)間內(nèi)進(jìn)行，你的目標(biāo)是完成盡可能多的任務(wù)。如果每次都選擇結(jié)束時(shí)間最早的任務(wù)，那么貪心算法就可以得到最優(yōu)解
• 分?jǐn)?shù)背包問(wèn)題
  • 給定一組物品和一個(gè)載重量，你的目標(biāo)是選擇一組物品，使得總重量不超過(guò)載重量，且總價(jià)值最大。如果每次都選擇性價(jià)比最高（價(jià)值 / 重量）的物品，那么貪心算法在一些情況下可以得到最優(yōu)解
• 股票買賣問(wèn)題
  • 給定一組股票的歷史價(jià)格，你可以進(jìn)行多次買賣，但如果你已經(jīng)持有股票，那么在賣出之前不能再買，目標(biāo)是獲取最大利潤(rùn)
• 霍夫曼編碼
  • 霍夫曼編碼是一種用于無(wú)損數(shù)據(jù)壓縮的貪心算法。通過(guò)構(gòu)建霍夫曼樹(shù)，每次選擇出現(xiàn)頻率最小的兩個(gè)節(jié)點(diǎn)合并，最后得到的霍夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度（即編碼長(zhǎng)度）最小
• Dijkstra 算法
  • 它是一種解決給定源頂點(diǎn)到其余各頂點(diǎn)的最短路徑問(wèn)題的貪心算法