第十三课 贪心、分治与动态规划初步——面对一个大问题到底应该“直接选”“拆开做”还是“记住以前算过的答案”这一课的目的是第一次建立“看到一个程序我能判断它大概在使用什么算法思想。”穷举、高精度、排序、递推、递归、贪心、分治、搜索、动态规划为CSP-J考试常见算法并把算法效率、时间复杂度作为算法知识的重要组成部分。因此这一课重点放在算法思想的辨认 简单程序模拟而不是一上来做复杂DP。一、第一部分什么是贪心先讲一个孩子非常容易理解的故事。买东西找零假设要找36元手里有20元 10元 5元 1元我们希望用尽可能少的钱。怎么办先拿最大的20还剩16再拿10还剩6再拿5还剩1最后1所以20 10 5 1一共4张。这就是一种非常典型的贪心思想二、什么叫“贪心”一句话每一步都选择当前看来最好的选择。也就是现在最好 ↓ 先选它 ↓ 再看下一步 ↓ 继续选当前最好所以孩子可以记贪心 只看眼前选择当前最优。三、生活中的贪心例如老师让大家排队进教室。如果目标是尽可能让更多同学先进入。我们可能优先安排当前最容易进入的同学。这就是一种“当前最优”的思想。但是这里要马上告诉孩子一个非常重要的问题“每一步最好”不一定意味着“最后最好”。这是理解贪心最重要的一道门槛。四、贪心并不是“随便选最大的”很多孩子会形成一个错误认识贪心就是每次选最大的。这是错误的。真正的定义是每一步根据问题的规则选择当前看来最有利的方案。有时候是选最大的有时候是选最小的有时候是选结束时间最早的有时候是选距离最近的所以贪心的核心是“局部最优选择”不是“永远选最大”。五、一个非常经典的贪心问题活动安排假设有几个活动活动开始结束A13B24C35D57E68我们希望一天安排尽可能多的活动。应该怎么选六、如果一开始选AA1~3接下来C3~5再D5~7所以A → C → D一共3个。七、为什么不是选开始最早的其实这里A1~3 B2~4A确实开始得更早。但“开始得早”并不是我们真正关心的东西。我们真正关心结束得早才能给后面的活动留下更多时间。所以贪心策略是每次选择结束时间最早、并且与当前方案不冲突的活动。八、这个思想非常重要我们应该慢慢体会问题目标 安排最多活动 ↓ 当前选择 哪个活动结束得最早 ↓ 为什么 结束越早 ↓ 剩余时间越多 ↓ 后面越可能安排更多活动这就是贪心策略的设计理由。九、典型贪心程序一个典型的活动安排程序可能是sort(a, a n, cmp); int last 0; int ans 0; for(int i 0; i n; i) { if(a[i].start last) { ans; last a[i].end; } }看到这个程序孩子要学会识别sort ↓ 按照某个规则排序 ↓ 从前往后 ↓ 每次选择满足条件的第一个这就是贪心。十、为什么先排序这是很多贪心题的共同特点。例如按照结束时间1~3 2~4 3~5 5~7 6~8排序之后从前往后扫描。每次能选 → 选 不能选 → 跳过所以孩子可以形成一个很有用的识别信号“排序 从前往后做局部最优选择”经常就是贪心。当然这只是识别线索不能作为绝对判断。十一、贪心最容易犯的错误例如硬币 1 3 4要凑6如果每次选择最大的4还剩2只能1 1一共4 1 1需要3枚。但是3 3只需要2枚。所以“每次选最大的”不一定得到最优答案。这就是同学们必须建立的第一道防线。十二、因此CSP-J中看到贪心不能只问“它是不是每次选最大的”而应该问“为什么这样选能够保证最终最优”如果只是“看起来不错”还不能证明它是贪心正确解法。十三、第二部分什么是分治现在换一个问题。假设老师给你1000个数字让你找最大值。一种方法一个一个看还有一种方法把1000个数字分成两组。500个 | 500个分别求最大值。得到左边最大值 右边最大值最后max(左边最大值, 右边最大值)这就是分治。十四、分治是什么意思三个字分、治、合。大问题 ↓ 分 ↓ 小问题 小问题 ↓ 分别解决 ↓ 合 ↓ 大问题答案所以分治就是把一个大问题分成若干个相似的小问题分别解决再合并结果。十五、生活中的分治老师让你整理100本书你可以50本给小明 50本给小红两个人分别整理。最后合起来就完成了。这就是分治思想。十六、归并排序就是分治这正好连接前面的第11课。归并排序8 3 5 1 7 2 6 4先分8 3 5 1 | 7 2 6 4继续分8 3 | 5 1 | 7 2 | 6 4继续8|3|5|1|7|2|6|4然后开始合并。3 8 1 5 2 7 4 6再1 3 5 8 2 4 6 7最后1 2 3 4 5 6 7 8所以归并排序 典型分治。十七、快速排序也是分治第11课已经学过快速排序。它的核心选择一个基准 ↓ 比它小的放左边 比它大的放右边 ↓ 左边继续排序 右边继续排序也就是大问题 ↓ 左边小问题 右边小问题 ↓ 分别解决所以快速排序也是典型分治。讲义中的复杂度部分也把快速排序列为典型的O(n log n)算法。十八、如何识别分治程序看到程序里出现solve(left, mid); solve(mid 1, right);或者quick_sort(l, mid); quick_sort(mid 1, r);我们可以初步判断这很可能是分治。因为一个大区间 ↓ 拆成两个小区间 ↓ 分别处理十九、分治和递归有什么关系这两个概念经常一起出现但不能混为一谈。递归 函数调用自己 分治 把大问题拆成小问题很多分治算法使用递归实现所以分治 ↓ 拆小问题 ↓ 递归解决但递归不一定是分治。例如fact(n)是递归但是并没有把问题拆成两个或多个子问题。二十、第三部分动态规划到底是什么1、爬楼梯假设有5级台阶每次可以走1级 或者 2级问一共有多少种走法我们从小的开始算。2、1级台阶只有1一种。所以f[1]13、2级台阶有11 2两种。所以f[2]24、3级台阶最后一步只有两种可能从第2级走1步f[2]从第1级走2步f[1]所以f[3]f[2]f[1]即f[3]2135、4级台阶同样f[4]f[3]f[2]所以f[4]3256、5级f[5]f[4]f[3]得到538所以答案8种。二十一、这其实和斐波那契很像我们发现f[1]1 f[2]2 f[3]3 f[4]5 f[5]8于是f[n]f[n-1]f[n-2]这说明很多动态规划问题本质上也是在研究“当前状态如何由以前的状态得到”。所以DP和第12课的递推有非常密切的关系。二十二、动态规划最核心的思想可以先给小学生一句话把大问题拆成很多小问题并把已经算过的小问题答案保存下来以后直接使用。关键词“保存答案”。二十三、为什么要保存继续看斐波那契递归fib(5) ├── fib(4) │ ├── fib(3) │ └── fib(2) └── fib(3)这里fib(3)计算了不止一次。如果fib(3)第一次已经算出2那么第二次遇到fib(3)就不要重新计算。直接拿答案这就是动态规划思想最朴素的来源。二十四、把“记住答案”写进程序例如int f[100]; f[1] 1; f[2] 1; for(int i 3; i n; i) { f[i] f[i-1] f[i-2]; }这里f[i]就是把已经计算出来的答案存起来。二十五、所以DP和递归的关系非常有意思普通递归大问题 ↓ 小问题 ↓ 再算 ↓ 小问题 ↓ 再算动态规划大问题 ↓ 小问题 ↓ 算一次 ↓ 保存 ↓ 以后直接拿可以记成DP “会记忆的递归思想”。这句话是帮助孩子理解的比喻并不是DP的严格定义但非常适合小学这个阶段。二十六、动态规划的三个关键词对于CSP-J初赛现阶段先让大家记① 状态我现在解决的是什么小问题例如f[i]表示到第i级台阶有多少种走法。② 状态转移也就是当前答案从哪里来例如f[i] f[i-1] f[i-2]③ 初始状态例如f[1]1 f[2]2所以DP 状态 状态转移 初始条件。二十七、这个公式千万不要死背大家最容易出现的问题“老师我记住了dp[i]dp[i-1]dp[i-2]是不是DP都这么写”当然不是。这个公式只是爬楼梯问题的状态转移。换一个问题公式马上变。真正要学的是“最后一步是什么”二十八、用“最后一步”寻找状态转移例如走到第i级台阶。最后一步只有从 i-1 走1步或者从 i-2 走2步所以dp[i] dp[i-1] dp[i-2]这就是状态转移。以后遇到DP题可以先问“这个状态最后一步是怎么来的”这是非常重要的思考方式。二十九、再举一个简单DP最大子段和例如1 -2 3 5 -1 2我们想找连续的一段和最大是多少比如3 5 - 1 2 9答案是9。这个问题先不要让孩子写复杂代码。只需要让孩子理解到第i个数的时候我能不能利用前面的答案可以定义dp[i]表示以第i个数结尾的最大连续子段和。那么dp[i] max( a[i], dp[i-1] a[i] )为什么因为包含a[i]的连续段要么从a[i]重新开始 要么接在前面的最优连续段后面这就是状态转移。三十、贪心和DP有什么区别这个非常重要。贪心现在选一个最好的 ↓ 以后不后悔关注当前选择。DP把不同的小问题答案保存下来 ↓ 综合以前的结果 ↓ 得到当前最优关注历史状态。三十一、一个特别形象的比喻贪心像走迷宫“我现在看哪条路最好就先走哪条。”DP像考试做题“以前遇到过类似问题我已经把答案记在笔记本上现在直接查。”所以贪心 眼睛看现在 DP 脑子记过去这个比喻非常适合小学生。三十二、贪心为什么可能失败回到硬币 1 3 4 目标 6贪心4 ↓ 1 ↓ 13枚。但是最优3 ↓ 32枚。所以贪心需要证明。而DPdp[0] dp[1] dp[2] ... dp[6]可以系统地把各种小问题答案保存下来。三十三、分治和DP有什么区别这也是非常容易混淆的地方。两者都是把大问题变小。但是分治大问题 ↓ 小问题A 小问题B ↓ 分别解决 ↓ 合并通常子问题之间相对独立。DP大问题 ↓ 很多小问题 ↓ 小问题可能重复 ↓ 保存答案 ↓ 避免重复计算所以“重复子问题”是理解DP的重要线索。三十四、四种算法思想放在一起现在让大家比较方法核心思想关键词递推前面的结果推出后面的结果f[i-1]递归函数自己调用自己f(n-1)贪心每一步选当前最优“选最好”分治大问题拆成小问题再合并“分 合”DP保存小问题答案避免重复dp[]这里特别提醒递推、递归不是与贪心、分治、DP完全同一层次的概念。递推/递归更多是在描述计算方式贪心/分治/DP更多是在描述解决问题的思想。初赛阶段先这样建立层次感即可。三十五、一个CSP-J程序阅读综合题来看int f[10]; f[1] 1; f[2] 2; for(int i 3; i 6; i) { f[i] f[i-1] f[i-2]; } cout f[6];程序阅读怎么办不要想算法名称。直接列表i 1 2 3 4 5 6 f[i] 1 2 3 5 8 13所以输出13这就是程序模拟 递推。三十六、再看一个贪心程序int ans 0; int last 0; sort(a, an, cmp); for(int i0;in;i) { if(a[i].start last) { ans; last a[i].end; } }看到sort ↓ for ↓ 满足条件就选择 ↓ 更新当前状态应该想到贪心。程序阅读重点不是让孩子证明算法而是按照排序后的顺序一次一次模拟。三十七、再看分治例如void solve(int l, int r) { if(l r) return; int mid (lr)/2; solve(l, mid); solve(mid1, r); merge(l, mid, r); }孩子看到solve(l,mid) solve(mid1,r)马上画[1,8] / \ [1,4] [5,8] / \ / \ [1,2][3,4][5,6][7,8]这就是分治树。三十八、再看DPdp[0] 0; for(int i1;in;i) { dp[i] dp[i-1] a[i]; }这里dp[i]保存的是前i个元素的某种答案。所以看到dp[]不要条件反射地认为“有数组就是DP。”真正要观察的是是否保存了子问题答案 当前状态是否依赖以前状态三十九、CSP-J程序阅读的“算法识别五问”以后大家拿到一道程序阅读题可以依次问第一问有没有反复使用以前的结果可能是递推 / DP第二问函数有没有调用自己可能是递归 / DFS / 分治第三问是不是每次都选择当前最好的可能是贪心第四问是不是把问题拆成左右两部分可能是分治第五问是不是在尝试很多可能可能是搜索 / 回溯四十、本课非常重要的“算法思想地图”一个大问题 │ ┌─────────────┼─────────────┐ ↓ ↓ ↓ 直接做 拆开做 尝试做 │ │ │ 贪心 分治 搜索 │ │ 当前选最好 分成小问题 │ ↓ 递归解决 大问题 ↓ 很多小问题 ↓ 小问题重复出现 ↓ 是 ↓ DP │ 保存以前的答案四十一、这一课最重要的不是会写DP对于初赛复习不用01背包 完全背包 区间DP 树形DP 状压DP这些内容以后专门讲。本课应该达到的是大家看到一段程序能够判断“它在干什么”。例如sort 每次选一个 ↓ 贪心 分成左右两个区间 ↓ 分治 f[i]依赖f[i-1] ↓ 递推 函数调用自己 ↓ 递归 dp[i]保存以前的小问题答案 ↓ 动态规划 不断尝试各种可能 ↓ 搜索这是本课真正的目标。四十二、本课CSP-J必背清单① 贪心每一步选择当前看来最优的方案。关键词局部最优但要注意局部最优不一定等于全局最优。② 分治把大问题分成若干个规模更小的同类问题分别解决再合并。关键词分 治 合典型归并排序 快速排序③ 动态规划初学阶段记把问题分成小问题把已经计算过的小问题答案保存下来避免重复计算。三个关键词状态 状态转移 初始状态④ 贪心 vs DP贪心 看现在 DP 记过去⑤ 分治 vs DP分治 拆开 → 分别做 → 合起来 DP 拆成小问题 → 保存答案 → 重复利用四十三、课堂回顾这一课内容比较多我们回顾下第1部分贪心 分治贪心是什么 ↓ 局部最优 ↓ 活动安排 ↓ 贪心程序模拟 ↓ 为什么贪心可能错误 ↓ 分治 ↓ 归并排序 ↓ 快速排序 ↓ 如何识别分治程序重点掌握“看到排序 选择”能想到贪心看到“拆成左右两个问题”能想到分治。第2部分动态规划初步为什么需要DP ↓ 斐波那契重复计算 ↓ 爬楼梯 ↓ 状态 ↓ 状态转移 ↓ 初始条件 ↓ DP程序阅读 ↓ 贪心 vs DP ↓ 分治 vs DP重点掌握“dp数组到底表示什么”四十四、给孩子的终极口诀贪心看现在每一步选最优。分治拆问题分开解决再合并。递推看前面一步一步推出后面。递归调用自己一定要有出口。搜索试可能走不通就回来。DP会记忆算过的答案不重算。贪心靠选择分治靠拆分DP靠状态。后面的复习路线到这里我们已经完成了一个非常重要的“算法思想闭环”第10课 算法与复杂度 ↓ 第11课 基础排序 ↓ 第12课 高效排序与二分 ↓ 第13课 栈、队列 ↓ 第14课 递推、递归、DFS、BFS ↓ ⭐ 第15课 贪心、分治、DP初步接下来第14课我们不要马上继续讲更复杂的算法而是进入CSP-J初赛特别容易考的第14课字符串、字符与ASCII——从char、字符串到字符串程序模拟 
长河君 · 2026/8/28 6:18:04 · 阅读 1.2k CSP-J 初赛（以满分为目标）：第十三课《贪心、分治与动态规划初步——面对一个大问题，到底应该“直接选”“拆开做”，还是“记住以前算过的答案”？》
第十三课 贪心、分治与动态规划初步——面对一个大问题到底应该“直接选”“拆开做”还是“记住以前算过的答案”这一课的目的是第一次建立“看到一个程序我能判断它大概在使用什么算法思想。”穷举、高精度、排序、递推、递归、贪心、分治、搜索、动态规划为CSP-J考试常见算法并把算法效率、时间复杂度作为算法知识的重要组成部分。因此这一课重点放在算法思想的辨认 简单程序模拟而不是一上来做复杂DP。一、第一部分什么是贪心先讲一个孩子非常容易理解的故事。买东西找零假设要找36元手里有20元 10元 5元 1元我们希望用尽可能少的钱。怎么办先拿最大的20还剩16再拿10还剩6再拿5还剩1最后1所以20 10 5 1一共4张。这就是一种非常典型的贪心思想二、什么叫“贪心”一句话每一步都选择当前看来最好的选择。也就是现在最好 ↓ 先选它 ↓ 再看下一步 ↓ 继续选当前最好所以孩子可以记贪心 只看眼前选择当前最优。三、生活中的贪心例如老师让大家排队进教室。如果目标是尽可能让更多同学先进入。我们可能优先安排当前最容易进入的同学。这就是一种“当前最优”的思想。但是这里要马上告诉孩子一个非常重要的问题“每一步最好”不一定意味着“最后最好”。这是理解贪心最重要的一道门槛。四、贪心并不是“随便选最大的”很多孩子会形成一个错误认识贪心就是每次选最大的。这是错误的。真正的定义是每一步根据问题的规则选择当前看来最有利的方案。有时候是选最大的有时候是选最小的有时候是选结束时间最早的有时候是选距离最近的所以贪心的核心是“局部最优选择”不是“永远选最大”。五、一个非常经典的贪心问题活动安排假设有几个活动活动开始结束A13B24C35D57E68我们希望一天安排尽可能多的活动。应该怎么选六、如果一开始选AA1~3接下来C3~5再D5~7所以A → C → D一共3个。七、为什么不是选开始最早的其实这里A1~3 B2~4A确实开始得更早。但“开始得早”并不是我们真正关心的东西。我们真正关心结束得早才能给后面的活动留下更多时间。所以贪心策略是每次选择结束时间最早、并且与当前方案不冲突的活动。八、这个思想非常重要我们应该慢慢体会问题目标 安排最多活动 ↓ 当前选择 哪个活动结束得最早 ↓ 为什么 结束越早 ↓ 剩余时间越多 ↓ 后面越可能安排更多活动这就是贪心策略的设计理由。九、典型贪心程序一个典型的活动安排程序可能是sort(a, a n, cmp); int last 0; int ans 0; for(int i 0; i n; i) { if(a[i].start last) { ans; last a[i].end; } }看到这个程序孩子要学会识别sort ↓ 按照某个规则排序 ↓ 从前往后 ↓ 每次选择满足条件的第一个这就是贪心。十、为什么先排序这是很多贪心题的共同特点。例如按照结束时间1~3 2~4 3~5 5~7 6~8排序之后从前往后扫描。每次能选 → 选 不能选 → 跳过所以孩子可以形成一个很有用的识别信号“排序 从前往后做局部最优选择”经常就是贪心。当然这只是识别线索不能作为绝对判断。十一、贪心最容易犯的错误例如硬币 1 3 4要凑6如果每次选择最大的4还剩2只能1 1一共4 1 1需要3枚。但是3 3只需要2枚。所以“每次选最大的”不一定得到最优答案。这就是同学们必须建立的第一道防线。十二、因此CSP-J中看到贪心不能只问“它是不是每次选最大的”而应该问“为什么这样选能够保证最终最优”如果只是“看起来不错”还不能证明它是贪心正确解法。十三、第二部分什么是分治现在换一个问题。假设老师给你1000个数字让你找最大值。一种方法一个一个看还有一种方法把1000个数字分成两组。500个 | 500个分别求最大值。得到左边最大值 右边最大值最后max(左边最大值, 右边最大值)这就是分治。十四、分治是什么意思三个字分、治、合。大问题 ↓ 分 ↓ 小问题 小问题 ↓ 分别解决 ↓ 合 ↓ 大问题答案所以分治就是把一个大问题分成若干个相似的小问题分别解决再合并结果。十五、生活中的分治老师让你整理100本书你可以50本给小明 50本给小红两个人分别整理。最后合起来就完成了。这就是分治思想。十六、归并排序就是分治这正好连接前面的第11课。归并排序8 3 5 1 7 2 6 4先分8 3 5 1 | 7 2 6 4继续分8 3 | 5 1 | 7 2 | 6 4继续8|3|5|1|7|2|6|4然后开始合并。3 8 1 5 2 7 4 6再1 3 5 8 2 4 6 7最后1 2 3 4 5 6 7 8所以归并排序 典型分治。十七、快速排序也是分治第11课已经学过快速排序。它的核心选择一个基准 ↓ 比它小的放左边 比它大的放右边 ↓ 左边继续排序 右边继续排序也就是大问题 ↓ 左边小问题 右边小问题 ↓ 分别解决所以快速排序也是典型分治。讲义中的复杂度部分也把快速排序列为典型的O(n log n)算法。十八、如何识别分治程序看到程序里出现solve(left, mid); solve(mid 1, right);或者quick_sort(l, mid); quick_sort(mid 1, r);我们可以初步判断这很可能是分治。因为一个大区间 ↓ 拆成两个小区间 ↓ 分别处理十九、分治和递归有什么关系这两个概念经常一起出现但不能混为一谈。递归 函数调用自己 分治 把大问题拆成小问题很多分治算法使用递归实现所以分治 ↓ 拆小问题 ↓ 递归解决但递归不一定是分治。例如fact(n)是递归但是并没有把问题拆成两个或多个子问题。二十、第三部分动态规划到底是什么1、爬楼梯假设有5级台阶每次可以走1级 或者 2级问一共有多少种走法我们从小的开始算。2、1级台阶只有1一种。所以f[1]13、2级台阶有11 2两种。所以f[2]24、3级台阶最后一步只有两种可能从第2级走1步f[2]从第1级走2步f[1]所以f[3]f[2]f[1]即f[3]2135、4级台阶同样f[4]f[3]f[2]所以f[4]3256、5级f[5]f[4]f[3]得到538所以答案8种。二十一、这其实和斐波那契很像我们发现f[1]1 f[2]2 f[3]3 f[4]5 f[5]8于是f[n]f[n-1]f[n-2]这说明很多动态规划问题本质上也是在研究“当前状态如何由以前的状态得到”。所以DP和第12课的递推有非常密切的关系。二十二、动态规划最核心的思想可以先给小学生一句话把大问题拆成很多小问题并把已经算过的小问题答案保存下来以后直接使用。关键词“保存答案”。二十三、为什么要保存继续看斐波那契递归fib(5) ├── fib(4) │ ├── fib(3) │ └── fib(2) └── fib(3)这里fib(3)计算了不止一次。如果fib(3)第一次已经算出2那么第二次遇到fib(3)就不要重新计算。直接拿答案这就是动态规划思想最朴素的来源。二十四、把“记住答案”写进程序例如int f[100]; f[1] 1; f[2] 1; for(int i 3; i n; i) { f[i] f[i-1] f[i-2]; }这里f[i]就是把已经计算出来的答案存起来。二十五、所以DP和递归的关系非常有意思普通递归大问题 ↓ 小问题 ↓ 再算 ↓ 小问题 ↓ 再算动态规划大问题 ↓ 小问题 ↓ 算一次 ↓ 保存 ↓ 以后直接拿可以记成DP “会记忆的递归思想”。这句话是帮助孩子理解的比喻并不是DP的严格定义但非常适合小学这个阶段。二十六、动态规划的三个关键词对于CSP-J初赛现阶段先让大家记① 状态我现在解决的是什么小问题例如f[i]表示到第i级台阶有多少种走法。② 状态转移也就是当前答案从哪里来例如f[i] f[i-1] f[i-2]③ 初始状态例如f[1]1 f[2]2所以DP 状态 状态转移 初始条件。二十七、这个公式千万不要死背大家最容易出现的问题“老师我记住了dp[i]dp[i-1]dp[i-2]是不是DP都这么写”当然不是。这个公式只是爬楼梯问题的状态转移。换一个问题公式马上变。真正要学的是“最后一步是什么”二十八、用“最后一步”寻找状态转移例如走到第i级台阶。最后一步只有从 i-1 走1步或者从 i-2 走2步所以dp[i] dp[i-1] dp[i-2]这就是状态转移。以后遇到DP题可以先问“这个状态最后一步是怎么来的”这是非常重要的思考方式。二十九、再举一个简单DP最大子段和例如1 -2 3 5 -1 2我们想找连续的一段和最大是多少比如3 5 - 1 2 9答案是9。这个问题先不要让孩子写复杂代码。只需要让孩子理解到第i个数的时候我能不能利用前面的答案可以定义dp[i]表示以第i个数结尾的最大连续子段和。那么dp[i] max( a[i], dp[i-1] a[i] )为什么因为包含a[i]的连续段要么从a[i]重新开始 要么接在前面的最优连续段后面这就是状态转移。三十、贪心和DP有什么区别这个非常重要。贪心现在选一个最好的 ↓ 以后不后悔关注当前选择。DP把不同的小问题答案保存下来 ↓ 综合以前的结果 ↓ 得到当前最优关注历史状态。三十一、一个特别形象的比喻贪心像走迷宫“我现在看哪条路最好就先走哪条。”DP像考试做题“以前遇到过类似问题我已经把答案记在笔记本上现在直接查。”所以贪心 眼睛看现在 DP 脑子记过去这个比喻非常适合小学生。三十二、贪心为什么可能失败回到硬币 1 3 4 目标 6贪心4 ↓ 1 ↓ 13枚。但是最优3 ↓ 32枚。所以贪心需要证明。而DPdp[0] dp[1] dp[2] ... dp[6]可以系统地把各种小问题答案保存下来。三十三、分治和DP有什么区别这也是非常容易混淆的地方。两者都是把大问题变小。但是分治大问题 ↓ 小问题A 小问题B ↓ 分别解决 ↓ 合并通常子问题之间相对独立。DP大问题 ↓ 很多小问题 ↓ 小问题可能重复 ↓ 保存答案 ↓ 避免重复计算所以“重复子问题”是理解DP的重要线索。三十四、四种算法思想放在一起现在让大家比较方法核心思想关键词递推前面的结果推出后面的结果f[i-1]递归函数自己调用自己f(n-1)贪心每一步选当前最优“选最好”分治大问题拆成小问题再合并“分 合”DP保存小问题答案避免重复dp[]这里特别提醒递推、递归不是与贪心、分治、DP完全同一层次的概念。递推/递归更多是在描述计算方式贪心/分治/DP更多是在描述解决问题的思想。初赛阶段先这样建立层次感即可。三十五、一个CSP-J程序阅读综合题来看int f[10]; f[1] 1; f[2] 2; for(int i 3; i 6; i) { f[i] f[i-1] f[i-2]; } cout f[6];程序阅读怎么办不要想算法名称。直接列表i 1 2 3 4 5 6 f[i] 1 2 3 5 8 13所以输出13这就是程序模拟 递推。三十六、再看一个贪心程序int ans 0; int last 0; sort(a, an, cmp); for(int i0;in;i) { if(a[i].start last) { ans; last a[i].end; } }看到sort ↓ for ↓ 满足条件就选择 ↓ 更新当前状态应该想到贪心。程序阅读重点不是让孩子证明算法而是按照排序后的顺序一次一次模拟。三十七、再看分治例如void solve(int l, int r) { if(l r) return; int mid (lr)/2; solve(l, mid); solve(mid1, r); merge(l, mid, r); }孩子看到solve(l,mid) solve(mid1,r)马上画[1,8] / \ [1,4] [5,8] / \ / \ [1,2][3,4][5,6][7,8]这就是分治树。三十八、再看DPdp[0] 0; for(int i1;in;i) { dp[i] dp[i-1] a[i]; }这里dp[i]保存的是前i个元素的某种答案。所以看到dp[]不要条件反射地认为“有数组就是DP。”真正要观察的是是否保存了子问题答案 当前状态是否依赖以前状态三十九、CSP-J程序阅读的“算法识别五问”以后大家拿到一道程序阅读题可以依次问第一问有没有反复使用以前的结果可能是递推 / DP第二问函数有没有调用自己可能是递归 / DFS / 分治第三问是不是每次都选择当前最好的可能是贪心第四问是不是把问题拆成左右两部分可能是分治第五问是不是在尝试很多可能可能是搜索 / 回溯四十、本课非常重要的“算法思想地图”一个大问题 │ ┌─────────────┼─────────────┐ ↓ ↓ ↓ 直接做 拆开做 尝试做 │ │ │ 贪心 分治 搜索 │ │ 当前选最好 分成小问题 │ ↓ 递归解决 大问题 ↓ 很多小问题 ↓ 小问题重复出现 ↓ 是 ↓ DP │ 保存以前的答案四十一、这一课最重要的不是会写DP对于初赛复习不用01背包 完全背包 区间DP 树形DP 状压DP这些内容以后专门讲。本课应该达到的是大家看到一段程序能够判断“它在干什么”。例如sort 每次选一个 ↓ 贪心 分成左右两个区间 ↓ 分治 f[i]依赖f[i-1] ↓ 递推 函数调用自己 ↓ 递归 dp[i]保存以前的小问题答案 ↓ 动态规划 不断尝试各种可能 ↓ 搜索这是本课真正的目标。四十二、本课CSP-J必背清单① 贪心每一步选择当前看来最优的方案。关键词局部最优但要注意局部最优不一定等于全局最优。② 分治把大问题分成若干个规模更小的同类问题分别解决再合并。关键词分 治 合典型归并排序 快速排序③ 动态规划初学阶段记把问题分成小问题把已经计算过的小问题答案保存下来避免重复计算。三个关键词状态 状态转移 初始状态④ 贪心 vs DP贪心 看现在 DP 记过去⑤ 分治 vs DP分治 拆开 → 分别做 → 合起来 DP 拆成小问题 → 保存答案 → 重复利用四十三、课堂回顾这一课内容比较多我们回顾下第1部分贪心 分治贪心是什么 ↓ 局部最优 ↓ 活动安排 ↓ 贪心程序模拟 ↓ 为什么贪心可能错误 ↓ 分治 ↓ 归并排序 ↓ 快速排序 ↓ 如何识别分治程序重点掌握“看到排序 选择”能想到贪心看到“拆成左右两个问题”能想到分治。第2部分动态规划初步为什么需要DP ↓ 斐波那契重复计算 ↓ 爬楼梯 ↓ 状态 ↓ 状态转移 ↓ 初始条件 ↓ DP程序阅读 ↓ 贪心 vs DP ↓ 分治 vs DP重点掌握“dp数组到底表示什么”四十四、给孩子的终极口诀贪心看现在每一步选最优。分治拆问题分开解决再合并。递推看前面一步一步推出后面。递归调用自己一定要有出口。搜索试可能走不通就回来。DP会记忆算过的答案不重算。贪心靠选择分治靠拆分DP靠状态。后面的复习路线到这里我们已经完成了一个非常重要的“算法思想闭环”第10课 算法与复杂度 ↓ 第11课 基础排序 ↓ 第12课 高效排序与二分 ↓ 第13课 栈、队列 ↓ 第14课 递推、递归、DFS、BFS ↓ ⭐ 第15课 贪心、分治、DP初步接下来第14课我们不要马上继续讲更复杂的算法而是进入CSP-J初赛特别容易考的第14课字符串、字符与ASCII——从char、字符串到字符串程序模拟