第1章概論

1.1算法概述

1.1.1什麼是算法

1.1.2算法描述

1.1.3算法和數據結構

1.1.4算法設計的基本步驟

1.2算法分析

1.2.1算法的時間復雜度分析

1.2.2算法的空間復雜度分析

1.3練習題

1.3.1單項選擇題

1.3.2問答題

1.3.3算法設計題

第2章常用數據結構及其應用

2.1線性表

2.1.1什麼是線性表

2.1.2vector向量容器

2.1.3STL通用算法

2.1.4list鏈表容器

2.2字符串

2.2.1什麼是字符串

2.2.2string字符串容器

2.3棧、隊列和雙端隊列

2.3.1什麼是棧、隊列和雙端
隊列

2.3.2deque雙端隊列容器

2.3.3queue隊列容器

2.3.4stack棧容器

2.4二叉樹和優先隊列

2.4.1二叉樹

2.4.2優先隊列

2.4.3priority_queue優先隊列
容器

2.5樹和並查集

2.5.1樹

2.5.2並查集

2.6圖

2.6.1圖基礎

2.6.2生成樹和小生成樹

2.6.3短路徑

2.6.4拓撲排序

2.7二叉排序樹和平衡二叉樹

2.7.1二叉排序樹

2.7.2平衡二叉樹

2.7.3集合容器set/multiset

2.7.4映射容器map/multimap

2.8哈希表

2.8.1什麼是哈希表

2.8.2哈希集合容器unordered_set

2.8.3哈希映射容器unordered_map

2.9設計好的數據結構

2.10練習題

2.10.1單項選擇題

2.10.2問答題

2.10.3算法設計題

2.11上機實驗題

2.11.1高效地插入、刪除和
查找

2.11.2一種特殊的隊列

2.11.3方塊操作

2.12在線編程題

第3章基本算法設計方法

3.1窮舉法

3.1.1窮舉法概述

3.1.2連續子序列和

3.1.3字符串匹配

3.1.4實戰——查找單詞
(POJ1501)

3.2歸納法

3.2.1歸納法概述

3.2.2直接插入排序

3.2.3樓梯問題

3.2.4猴子摘桃子問題

3.2.5實戰——骨牌鋪方格
(HDU2046)

3.3迭代法

3.3.1迭代法概述

3.3.2簡單選擇排序

3.3.3素

3.3.4求冪集

3.3.5實戰——子集(LeetCode78)

3.4遞歸法

3.4.1遞歸法概述

3.4.2冒泡排序

3.4.3求全排列

3.4.4實戰——展開字符串
(HDU1274)

3.5遞推式計算

3.5.1直接展開法

3.5.2遞歸樹方法

3.5.3主方法

3.6練習題

3.6.1單項選擇題

3.6.2問答題

3.6.3算法設計題

3.7上機實驗題

3.8在線編程題

第4章分治法

4.1分治法概述

4.1.1什麼是分治法

4.1.2分治法框架

4.2求解排序問題

4.2.1快速排序

4.2.2查找一個序列中第k小的

4.2.3歸並排序

4.2.4實戰——求逆序數
(POJ2299)

4.3求解查找問題

4.3.1查找素

4.3.2二分查找

4.3.3查找兩個等長有序序列的
中位數

4.3.4查找問題

4.3.5*實戰——有序數組中的

4.4求解組合問題

4.4.1連續子序列和

4.4.2棋盤覆蓋問題

4.4.3循環日程安排
問題

4.4.4求近點對距離

4.4.5實戰——求兩組點之間的
近點對(POJ3714)

4.5求xn和An問題

4.5.1求xn問題

4.5.2求An問題

4.5.3實戰——用矩陣快速冪求
Fibonacci數列(POJ3070)

4.6練習題

4.6.1單項選擇題

4.6.2問答題

4.6.3算法設計題

4.7上機實驗題

4.8在線編程題

第5章回溯法

5.1回溯法概述

5.1.1問題的解空間

5.1.2什麼是回溯法

5.1.3回溯法算法的框架

5.1.4回溯法算法的時間
分析

5.2基於子集樹框架的問題求解

5.2.1子集和問題

5.2.2簡單裝載問題

5.2.30/1背包問題

5.2.4n皇後問題

5.2.5任務分配問題

5.2.6出棧序列

5.2.7圖的m著色

5.2.8實戰——救援問題
(HDU1242)

5.3基於排列樹框架的問題求解

5.3.1任務分配問題

5.3.2貨郎擔問題

5.3.3實戰——素的全
排列Ⅱ(LeetCode47)

5.4練習題

5.4.1單項選擇題

5.4.2問答題

5.4.3算法設計題

5.5上機實驗題

5.6在線編程題

第6章分支限界法

6.1分支限界法概述

6.1.1什麼是分支限界法

6.1.2分支限界法的設計要點

6.1.3分支限界法的時間分析

6.2廣度優先搜索

6.2.1廣度優先搜索概述

6.2.2實戰——抓牛問題
(POJ3278)

6.2.3實戰——推箱子
(HDU1254)

6.2.4實戰——腐爛的橘子
(LeetCode994)

6.3隊列式分支限界法

6.3.1隊列式分支限界法概述

6.3.2圖的單源短路徑

6.3.30/1背包問題

6.3.4實戰——網格中的短
路徑(LeetCode1293)

6.4優先隊列式分支限界法

6.4.1優先隊列式分支限界法
概述

6.4.2圖的單源短路徑

6.4.3實戰——小體力消耗路
徑(LeetCode1631)

6.4.40/1背包問題

6.4.5任務分配問題

6.4.6貨郎擔問題

6.5練習題

6.5.1單項選擇題

6.5.2問答題

6.5.3算法設計題

6.6上機實驗題

6.7在線編程題

第7章貪心法

7.1貪心法概述

7.1.1什麼是貪心法

7.1.2貪心法求解問題具有的
性質

7.1.3貪心法的一般求解過程

7.2求解組合問題

7.2.1活動安排問題Ⅰ

7.2.2實戰——加工木棍
(POJ1065)

7.2.3求解背包問題

7.3求解圖問題

7.3.1用Prim算法構造小生
成樹

7.3.2用Kruskal算法構造小
生成樹

7.3.3實戰——建設道路
(POJ3625)

7.3.4用Dijkstra算法求單源
短路徑

7.3.5實戰——短路徑問題
(HDU3790)

7.4求解調度問題

7.4.1不帶懲罰的調度問題

7.4.2帶懲罰的調度問題

7.4.3實戰——趕作業
(HDU1789)

7.5哈夫曼編碼

7.5.1哈夫曼樹和哈夫曼編碼

7.5.2實戰——後一塊石頭的
重量(LeetCode1046)

7.6練習題

7.6.1單項選擇題

7.6.2問答題

7.6.3算法設計題

7.7上機實驗題

7.8在線編程題

第8章動態規劃

8.1動態規劃概述

8.1.1從一個簡單示例入門

8.1.2動態規劃的原理

8.1.3動態規劃求解問題的性質
和步驟

8.1.4動態規劃與其他方法的
比較

8.2一維動態規劃

8.2.1連續子序列和

8.2.2實戰——子序列和
(LeetCode53)

8.2.3長遞增子序列

8.2.4*活動安排問題Ⅱ

8.3二維動態規劃

8.3.1三角形小路徑和

8.3.2實戰——下降路徑小
和(LeetCode931)

8.4三維動態規劃

8.4.1用Floyd算法求多源短
路徑

8.4.2*雙機調度問題

8.5字符串動態規劃

8.5.1長公共子序列

8.5.2編輯距離

8.6背包動態規劃

8.6.10/1背包問題

8.6.2完全背包問題

8.6.3實戰——零錢兌換
(LeetCode322)

8.6.4*多重背包問題

8.7樹形動態規劃

8.7.1實戰——慶祝晚會
(HDU1520)

8.7.2實戰——找礦
(LeetCode337)

8.8區間動態規劃

8.8.1實戰——戳氣球
(LeetCode312)

8.8.2實戰——長回文
子串(LeetCode5)

8.9練習題

8.9.1單項選擇題

8.9.2問答題

8.9.3算法設計題

8.10上機實驗題

8.11在線編程題

第9章NP完全問題

9.1P類和NP類

9.1.1易解問題和難解問題

9.1.2判定問題

9.1.3P類

9.1.4NP類

9.2多項式時間變換和NP完全
問題

9.2.1多項式時間變換

9.2.2NP完全性及其性質

9.2.3個NP完全問題

9.2.4其他NP完全問題

9.3練習題

9.3.1單項選擇題

9.3.2問答題

參考文獻

黨的二十大報告指出，教育、科技、人纔是全面建設社會主義現代化國家的基礎性、戰略性支撐。必須堅持科技是生產力、人纔是資源、創新是動力，深入實施科教興國戰略、人纔強國戰略、創新驅動發展戰略，開闢發展新領域新賽道，不斷塑造發展新動能新優勢。

用計算機求解問題是將特定問題的求解過程轉換為計算機可以執行的程序。能夠設計好的程序是計算機專業學生的基本功。在計算機教學體繫中涉及編程的主要課程有“高級程序設計語言”“數據結構”“算法設計與分析”。這些課程相互承接，程序設計語言是求解問題的工具，數據結構是求解問題的基礎，算法設計是求解問題的關鍵。

“算法設計與分析”課程是計算機科學與技術等專業的專業必修課，課程目的是通過學習、理解並掌握算法設計的主要策略和算法復雜性分析的方法，能熟練運用各種數據結構和常用算法策略設計高效算法，培養學生分析問題和解決復雜工程問題的能力，為學生進一步學習後續課程奠定良好的基礎。

本書是編者長期從事“數據結構”“算法設計與分析”課程本科生和研究生教學的經驗總結，凝聚了編者的教學體會和理念。

1. 本書內容

全書由9章構成，各章內容如下。

第1章為概論，介紹算法的概念、算法描述方法、算法設計步驟和算法時空分析方法。

第2章為常用數據結構及其應用，結合STL介紹線性表、字符串、棧、隊列、雙端隊列、樹、二叉樹、二叉排序樹、平衡二叉樹、優先隊列、並查集、圖和哈希表等數據結構的原理和應用，討論如何針對求解問題設計好的數據結構。

第3章為基本算法設計方法，介紹窮舉法、歸納法、迭代法和遞歸法等常用的算法設計方法，討論遞推式計算等基本算法分析方法。

第4章為分治法，介紹分治法的原理和框架，討論利用分治法求解排序問題、查找問題、組合問題、求xn和An問題，包括求連續子序列和、字符串匹配、樓梯問題、求冪集和求全排列等典型算法。

第5章為回溯法，介紹解空間概念和回溯法框架，根據解空間的類型分別討論基於子集樹框架的問題求解方法和基於排列樹框架的問題求解方法，包括子集和問題、簡單裝載問題、0/1背包問題、n皇後問題、任務分配問題、出棧序列、圖的m著色和貨郎擔問題等典型算法。

第6章為分支限界法，介紹分支限界法的要點和框架，討論廣度優先搜索、隊列式分支限界法和優先隊列式分支限界法，包括圖的單源短路徑、0/1背包問題、任務分配問題和貨郎擔問題等典型算法。

第7章為貪心法，介紹貪心法的策略和要點，討論采用貪心法求解組合問題、圖問題、調度問題和哈夫曼編碼，包括活動安排問題Ⅰ、Prim、Kruskal、Dijkstra和不帶/帶懲罰的調度問題等典型算法。

第8章為動態規劃，介紹動態規劃的原理和要點，討論一維動態規劃、二維動態規劃、三維動態規劃、字符串動態規劃、背包動態規劃、樹形動態規劃和區間動態規劃算法設計方法，包括連續子序列和、長遞增子序列、活動安排問題Ⅱ、三角形小路徑和、Floyd算法、雙機調度、長公共子序列、編輯距離、0/1背包問題、完全背包問題和多重背包問題等典型算法。

第9章為NP完全問題，介紹P類、NP類和NP完全問題。

書中帶“*”號的部分作為選學內容。

2. 本書特色

本書具有如下鮮明特色： 

（1） 由淺入深，循序漸進。每種算法策略從設計思想、算法框架入手，由易到難地講解經典問題的求解過程，使讀者既能學到求解問題的方法，又能通過對算法策略的反復應用掌握其核心原理，以收到融會貫通之效。

（2） 示例豐富，重視啟發。書中列舉大量的具有典型性的求解問題，深入剖析采用相關算法策略求解的思路，展示算法設計的清晰過程，並舉一反三，激發學生學習算法設計的興趣。

（3） 注重求解問題的多維性。同一個問題采用多種算法策略實現，例如任務分配問題采用基於子集樹框架和排列樹框架以及分支限界法求解，0/1背包問題采用回溯法、分支限界法和動態規劃求解等。通過不同算法策略的比較，使學生更容易體會到每種算法策略的設計特點和各自的優缺點，以提高算法設計的效率。

（4） 強調實踐和動手能力的培養。書中以實戰形式討論了部分在線編程題的設計過程，包括求解問題的相關知識點、完整可通過的程序代碼和提交結果，這些實戰題來自力扣中國、北京大學POJ和杭州電子科技大學HDU網站，讓學生體會到“學以致用”和解決實際問題的樂趣。

（5） 本書配套有《算法設計與分析基礎（C 版）學習和實驗指導》（李春葆等，清華大學出版社），涵蓋所有練習題、上機實驗題和在線編程題的參考答案。

3. 教學資源

為了方便教師教學和學生學習，本書提供了全面而豐富的教學資源，內容如下。 

（1） “算法設計與分析”課程教學大綱（含課程思政）和電子教案： 包含教學目的、課程內容和學時分配（42學時），以及各章的課程思政要點和每個課時的教學內容安排。

（2） 教學PPT： 提供全部教學內容的精美PPT課件（947頁），供任課教師在教學中使用。

（3） 源程序代碼： 所有源程序代碼按章組織，例如ch3文件夾存放第3章的源程序代碼，其中perm.cpp為求全排列的源程序代碼，Example\\\\exam33.cpp為例33的源程序代碼，HDU1274.cpp為實戰題HDU1274的源程序代碼。

（4） “算法設計與分析”實驗課程教學大綱： 包含課程介紹、教學目的、實驗基本要求與方式、實驗報告、實驗內容與學時分配（15～21學時），以及每個實驗可供選擇的單機實驗題和在線編程題。

（5） 本書配套有絕大部分知識點的教學視頻，視頻采用微課碎片化形式組織（含96個小視頻，累計超過20小時）。

資源下載提示

課件等資源： 掃描封底的“課件下載”二維碼，在公眾號“書圈”下載。

素材（源碼）等資源： 掃描目錄上方的二維碼下載。

在線作業： 掃描封底的作業繫統二維碼，登錄網站在線做題及查看答案。

視頻等資源： 掃描封底的文泉雲盤防盜碼，再掃描書中相應章節的二維碼，可以在線學習。

本書第1、3、4章由中國勞動關繫學院陳良臣編寫，第2章和第9章由武漢大學喻丹丹編寫，第5～8章由武漢大學李春葆編寫，李春葆完成全書的規劃和統稿工作。本書的出版得到清華大學出版社魏江江分社長的全力支持，王冰飛老師給予精心編輯，LeetCode、POJ和HDU網站提供了無私的幫助，編者在此一並表示衷心感謝。

盡管編者不遺餘力，但由於水平所限，本書仍可能存在不足之處，敬請教師和同學們批評指正。

編者
2023年4月