【站务】违规公示

【游戏】故事接龙

故事接龙游戏已经重新开启，点我 来玩一个故事接龙的游戏！ 每人说一句话，然后接龙 我是作者我先来：有一天，一个人正在悠闲地散步... 感谢AC君点赞！

码上开聊VOL.2 勤勉笃行-吴泽均

码上开聊 欢迎来到码上开聊！这是一个属于编程少年的花式聊天角，带你一起解锁大佬们的神仙操作、逆袭时刻和刷题“翻车”故事！在这里，每一个代码少年都在用青春和坚持“码”出自己的高光时刻！ 本期第2话，我们请来了吴泽均！他凭21次提交全红却不放弃的劲头，硬是AC了一道题，告诉我们：编程，拼的就是这口气！赶紧上车，听听他的访谈吧！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ VOL.2 勤勉笃行-吴泽均 > 个人档案 * 姓名：吴泽均 * 年级：初一 * 校区：苏州新光天地校区 * 爱好：编程、画画、刻橡皮章、听音游音乐 * 社区主页：ACGO个人主页 * 获奖经历： 2024年CSP-J/S（江苏）：普及组初赛一等奖，复赛二等奖。提高组初赛二等奖，复赛三等奖。 2024年全国青少年信息素养大赛总决赛：算法创意实践挑战赛小学组一等奖。 2024年蓝桥杯全国青少年总决赛：C++C++C++中级创意编程组三等奖。 2024年蓝桥杯青少年江苏赛区：C++C++C++中级创意编程组一等奖。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 高能访谈 Q1 HI，你是什么时候开始学编程的？最开始觉得难吗？ 吴泽均： Q2 从PYTHON转到C++的过程对你来说有难度吗？是怎么适应的？ 吴泽均：一开始确实不情愿，因为刚刚学完Python的L2，C刚接触时觉得“<<”和“>>”特别绕，还记得那次是在苏州某机构（非小码王）的冬令营被讲得一头雾水。但后来爸爸和我商量，觉得C在竞赛里会更有前途，就决定尝试一下。不过现在我还是会做些Python的项目。 Q3 小码王集训营的经历对你有影响吗？ 吴泽均：影响挺大的。2023年与2024年，我参加了两次小码王的集训营（X03和X02），有一次模拟初赛考得不太好，主要是我轻敌了，之前考得好就有点放松。后来反思觉得，不管之前成绩如何，正式比赛都不能掉以轻心。这次经历让我对比赛更重视，也更加用心。 Q4 在集训营的生活上有没有不适应的地方？怎么克服的？ 吴泽均：刚到集训营时有点不适应，白天强度高，晚上休息不太好。后来我自己调整作息，晚上尽量早睡，早上尽量早起，这样渐渐适应了强度大的学习节奏。可惜十天的相处太短，我还在社区发了一篇帖子纪念。 Q5 听说你在ACGO上解决了不少题目，有没有特别有挑战的？ 吴泽均：有的，比如“A592 搬寝室”这道题让我印象深刻。我提交了21次都错了，本来的思路是用贪心算法，样例和自测都过了，但提交全红。后来换了思路，找到了重叠部分的最大数，终于解出来了！这道题让我明白，坚持是很重要的。 Q6 刷题时你有什么特别的学习方法吗？ 吴泽均：每天有时间我都会刷题，大概每天一个多小时吧，主要是因为喜欢。我还用Excel表记录刷题进度，把ACGO上橙题、黄题、绿题都标出来，每做完一道就勾掉，成就感满满！ Q7 除了编程，你平时还喜欢做些什么？ 吴泽均：我还喜欢画画和刻橡皮章之类的美术活动，特别放松。编程的时候我也会听音游的背景音乐，感觉更有节奏感。 Q8 对未来的编程学习有什么目标吗？ 吴泽均：希望通过编程获得择校优势，目标是考上理想的高中。未来得加强自学能力，少依赖老师。对编程职业也很有兴趣，可能会考虑IT行业！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 访谈结语 如果你也对编程有兴趣，欢迎和他一起加入ACGO，刷题、讨论、交流经验，一起在编程的世界里不断进步吧！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 往期访谈 VOL.1-镇站之宝Macw

码上开聊VOL.3 未来无限-王子翾

码上开聊 欢迎来到码上开聊！这是一个属于编程少年的花式聊天角，带你一起解锁大佬们的神仙操作、逆袭时刻和刷题“翻车”故事！在这里，每一个代码少年都在用青春和坚持“码”出自己的高光时刻！ 🎉 欢迎来到「码上开聊」Vol.3！在本期访谈中，我们将走近年仅初二、编程经验丰富的王子翾（社区昵称：Sanssssss），聆听他如何在小学二年级便踏上了编程之旅，并一路收获奖项的成长故事。让我们一起了解这位充满活力的同学吧！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 码上开聊VOL.3 未来无限-王子翾 > 个人档案 * 姓名：王子翾 * 社区昵称：Sanssssss * 年级：初二 * 校区：成都牛市口校区 * 编程起点：小学二年级学Scratch，三年级学Python与C++ * 兴趣：编程、游戏设计、信息安全 * 社区主页：ACGO个人主页 * 获奖经历： * 2024年：CSP-J 一等奖（第二轮）、CSP-S 三等奖（第一轮）、蓝桥杯C++省二 * 2023年：CSP-J 二等奖（第一轮）、第五届四川省青少年创意编程与智能设计比赛决赛一等奖 * 2022年：CSP-J 二等奖 （第一轮）、蓝桥杯Python省赛二等奖 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 高能访谈 Q1 你是从什么时候开始学编程的？ 王子翾 ：我从小学二年级开始学Scratch，现在初二，三年级学的Python，过了一年才开始学C++。 Q2 从小就喜欢编程么？ 王子翾 ：小时候觉得编程挺好玩，主要是图形化编程很有意思。现在更多的是刷题成功后觉得很有成就感，像是一种“能力变强”的感觉。我觉得既然花了很多时间学编程，不坚持下去感觉会浪费掉之前的努力。 Q3 你从PYTHON过渡到C++难吗？是怎么克服的？ 王子翾 ：一开始确实有点难，特别是动态规划的部分，刚开始一直搞不懂。后来听了同龄人的思路，再刷几道类似的题，慢慢就理解了。 Q4 平常都怎么安排刷题时间？在哪些平台刷题？ 王子翾 ：每周日我会给自己半天时间刷题，除非有事一般都会刷。周一到周五看作业进度，有空就上ACGO打比赛。一开始是在洛谷，最近在ACGO上打比赛。 Q5 有什么印象深刻的题么？ 王子翾 ：ACGO挑战赛8的第五题A27805.宏量运算 ，我想了三天才做出来。 Q6 你参加了几次集训营？有什么感受？ 王子翾 ：参加过多次集训营，我觉得集训营能把大家聚在一起，都是热爱编程的同龄人，能一起学，也能交流做题的技巧，还能查缺补漏，对我帮助挺大的。虽然我是在成都学习的，不过每年都会去杭州参加集训。我觉得杭州是总部，教得更扎实。 Q7 集训营里有没有特别难忘的事情？ 王子翾 Q8 用一句话形容自己的性格？ 王子翾 ：我觉得我的性格像水一样吧，因为我从小到大就没有真正生气过，所以我觉得我的性格像水。 Q9 学习C++过程中有什么难忘的经历吗？ 王子翾 ：最难忘的一件事是在刚入门的时候发现万能头文件，因为只需要这一个头文件就可以顶替其他大部分头文件，所以当时特别激动。后来，我还将一些想法写成了《我重生异世界，觉醒最强系统》系列。 王子翾文章：我重生异世界，觉醒最强系统（2） Q10 有什么编程经验可以分享给刚入门的选手？ 王子翾 ：就是不要轻易放弃，然后遇到对你来说特别困难，完全没有思路的不要死磕，因为如果连思路都没有就几乎不可能做对，这时候就可以问问老师或同学，也可以去社区问问大佬，很多都是很乐意教萌新的。 来源：通义万象 本人照片图生图 Q11 未来编程学习上有什么计划？有考虑什么职业方向吗？ 王子翾 ：明年想冲一下S组的奖，然后尝试争取进省队。希望高中阶段能够继续提高吧。职业的话 可能会考虑游戏设计或者信息网络安全这一块吧，两个方向都挺感兴趣的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 访谈结语 如果你也对编程有兴趣，欢迎和他一起加入ACGO，刷题、讨论、交流经验，一起在编程的世界里不断进步吧！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 往期访谈 VOL.1-镇站之宝Macw VOL.2-勤勉笃行吴泽均

关于欢乐赛#33的举报

原举报 惩罚 当事人发言： 首先让我们捋一捋，竞赛结尾有标明：首次作弊禁言15天并取消奖励，但这边很明确的能看到只禁言3天。如果真的是作弊，为什么只有3天？再者，公告曰：T5、T6与AI相似度达100%。AI的随机方式都不能保证达到与AI100%相似度，诸位仍然觉得这是使用AI吗？又如，如果在排位赛作弊会降低排位分，即使不在评分范围内也应有相对应在排位分上的惩罚，主页信息却不见#33有掉分。综上所述，此计不过是AC君为避免事态扩大与老师演的苦肉计罢了 所以说AC君有自己的反作弊系统，有的时候如果存在其他合理且合规的可能性不用先写举报帖，直接私聊向AC君汇报/核对情况。如果闹了乌龙对谁都不好。 有大佬点赞了，帮帮忙吧（点个赞发个顶都可以） 从12.4以后 处罚更为酌情处理

互动#8｜如果转生异世界写代码

🚀互动#8 ：如果转生异世界写代码 😎 hi，要是转生到异世界，你会怎样？ 你能利用代码知识干啥？ 快来一起脑洞大开吧！ 🎤脑洞分享区 分享你在异世界运用代码的奇思妙想，职业规划、冒险策略等都可。 🎁 话题奖励 * 奖励设置：选 3 位 最强脑洞送 ACGO 2周年贴纸。 * 参与方式：在评论区畅抒己！ ⏰ 活动时间 * 结束时间: 12月15日 * 奖励公告 ：12月16日 🎁获奖名单 ID 昵称 4326909 天之神_ZDZL_复仇者_6. 2771152 AC是我的0.o 2454098 复仇者_燃烬

故事接龙-重开

以前那个没用了，全被他们的图片占了！ 这次来重新接龙！！ 如果发图片，联系AC君 另外禁止给评论点赞！

32场信奥讲座#1 ｜主讲人：肖艺能

32场信奥讲座#1 ｜主讲人：肖艺能 还在羡慕竞赛大佬的神仙履历？快来围观本周的主讲人，肖艺能老师，这位简直是履历控的天花板！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ✨ 主讲人简介 * 现任：北京大学信息技术高等研究院研究员（正高级）、智能教育实验室主任 * 教育背景： * 北京大学医学人文学院博士后 * 北京大学法学博士 * 北京大学理学学士 * 曾作为访问学者赴斯坦福大学与剑桥大学深造 * 相关经历： * 国际化学奥赛金牌教练，亲手培养了 3 名国际化学奥赛金牌得主 * 国内十余所知名中学（如杭州二中、北大附中）特聘专家，聚焦科技创新与拔尖人才培养 * 世界机器人大赛专家委员会常务委员，教育部白名单赛事专家 * 多年从事北京大学本科招生工作，深谙顶尖高校选拔之道 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这周肖老师将为大家分享他在竞赛辅导、科技创新人才培养中的独家见解，干货满满，绝不容错过！ 点此了解32场硬核信奥讲座>>

一文讲清动态规划的本质

一文讲清动态规划的本质 动态规划 Dynamic Programming (DP) 是算法领域的核心思想之一，却同时也是让许多学习者感到棘手的难点之一。动态规划的难点在于它不是简单的数学推导，也不单纯考验人们的程序设计能力，而更像是一种从思维方式到问题建模的一次深刻训练。 本文将从动态规划的定义出发，深入探讨动态规划的本质、应用场景、核心特点、解题思路以及如何逐步提升解决动态规划问题的能力。 动态规划的定义和应用：将大问题分解成许多小问题 动态规划的核心思想可以被概括为一句话：将一个复杂的问题分解成多个简单的子问题，并通过保存子问题的解来避免重复计算，从而提高求解效率。 换句话说，动态规划适用于解决以下两类问题： 1. 最优子结构问题：所谓的最优子结构问题，就是一个最优解可以通过其子问题的最优解而构成。 2. 子问题重叠问题：多个子问题在递归的过程中会重复出现，并且会被多次计算到。 E.G. 01 - 斐波那契数列 I\MATHRM{I}I 我们都知道斐波那契的通项公式是 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)。以计算斐波那契数列的第五项 F(5)F(5)F(5) 为例，很显然，F(5)F(5)F(5) 就是我们需要求解的大问题，而这个大问题可以被逐步分解为两个小问题，即 F(4)F(4)F(4) 和 F(3)F(3)F(3) 。只要我们知道了 F(4)F(4)F(4) 和 F(3)F(3)F(3)，那么我们就可以将这两项相加来得到最终的结果。这个就是最优子结构的体现。 那什么时候会出现子问题重叠呢？我们不妨用代码来实现斐波那契数列： 这是一个很简单的递归算法。通过模拟递归算法我们可以画出一个递归图： 通过观察这个图可以发现，在计算 F(5)F(5)F(5) 的时候，F(3)F(3)F(3) 被 F(5)F(5)F(5) 调用过一次，同时又被 F(4)F(4)F(4) 调用一次。相同地，F(2)F(2)F(2) 被 F(3)F(3)F(3) 调用了两次，被 F(4)F(4)F(4) 也调用了一次。我们可以发现这个图中有很多的重复计算，这会大大浪费程序的运行时间。然而这就是所谓的子问题重叠问题。 针对这类型的问题，有什么解决方案呢？最直接的方法就是把已经计算过的答案保存下来，下次再调用的时候直接获取结果就可以了，这种方法就是大家常说的“记忆化”。记忆化搜索的代码如下： 这个代码与普通斐波那契数列唯一的区别就是增加一个 memo 数组，判断某一个值是否已经被计算过。如果已经被计算过就直接返回，而不需要继续递归来消耗时间。 而另一种解决办法就是“递推“，我们可以从小到大，先计算 F(0)F(0)F(0) 和 F(1)F(1)F(1) 并把答案保存下来，计算 F(2)F(2)F(2) 的时候就可以立刻通过将 F(0)F(0)F(0) 和 F(1)F(1)F(1) 相加得到结果。这种递推的做法就是所谓的动态规划思想。而这么做的代码也更加简洁： 因此，动态规划的核心思想就是通过 记录 和 重用 子问题的解，避免重复计算，从而提高求解效率。动态规划是一种典型的 拿空间换时间 的思想（毕竟现在的社会，时间成本比空间成本高太多了）。 > 动态规划与分治思想的主要区别就是分治算法主要应用于子问题不重叠的问题，而针对子问题重叠的问题，动态规划是一个更好的选择。 动态规划的性质 动态规划的三个基本性质是：最优子结构、子问题重叠 以及 无后效性。前两个性质已经在第一部分提及过了，本部分主要讲解无后效性。 无后效性，又称马尔可夫性，这意味着某阶段的状态一旦确定，就不接受该状态之后决策的影响。即，某状态以后的过程不会影响之前的状态，只与当前的状态有关。用一句话概括就是“过去的事情不会影响未来，只关注当前的状态”。 除了无后效性，动态规划的另一个核心在于 最优性原理，即一个最优解包含其子问题的最优解。这一原理是由理查德·贝尔曼（Richard Bellman）提出。最优性原理是动态规划思想的理论基石。 E.G. 02 - 斐波那契数列 II\MATHRM{II}II 回到原本斐波那契数列场景，当计算 F(5)F(5)F(5) 时，答案只依赖于当前状态 F(4)F(4)F(4) 和 F(3)F(3)F(3) 的值，与更早的历史状态无关。这就是为什么，我们在计算 F(5)F(5)F(5) 的时候可以直接使用 F(3)F(3)F(3) 和 F(4)F(4)F(4) 之前被计算出来的结果相加得到答案，而不是从 F(1)F(1)F(1) 和 F(0)F(0)F(0) 开始重新计算。 与此同时，在具有无后效性的场景中，一旦某一个状态的值已经被计算下来并可以转移到下一个状态时，这个状态将不会再被改变。换句话说，某状态以后的过程不会影响以前计算出来的状态，只与当前的状态有关。 无后效性是避免重复计算子问题的前提条件。 动态规划和递归的关联 在看到这里，你会发现动态规划和递归这两个思想有着异曲同工之妙。事实上，大多数的动态规划问题都可以使用记忆化搜索（递归）来解决。动态规划和暴力递归的关键区别如下： * 递归：通过函数自调用，将问题分解为子问题，直到达到基本情况。递归可能导致大量重复计算，效率较低。 * 动态规划：通过记录已解决的子问题的解，避免重复计算。动态规划通常采用自底向上的方式，效率更高。 因此广义而言。带有记忆化搜索的递归算法也可以被称之为是动态规划。 解决动态规划问题的基本思路 解决动态规划问题的基本思路如下： 步骤一：确定不同的阶段和变量 根据题目的特性，我们可以把一个问题拆解成小问题，将一个小问题拆分成一个个次小问题，以此类推。那么在这之中，每一个需要解决的问题就被称之为一个阶段（状态）。因此对于动态规划问题，第一步需要做的就是尝试如何把大问题分解成许多个有关联的问题。同时，我们需要找到每一个阶段之间都是通过什么变量关联起来的。在斐波那契数列问题中，变量就是斐波那契数列的项数。 步骤二：确定状态转移方程式 在动态规划中，我们把每一个“阶段”称之为一个状态。例如，F(5)F(5)F(5) 就可以被称之为是一个状态。我们需要搞清楚大问题的状态和小问题的状态之间的关联。 在斐波那契数列中，这个关联就是：序列的第 iii 项为序列的第 i−1i-1i−1 和第 i−2i-2i−2 项的和。用数学表示就是 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)。在其他的例子中（更加现实一点的），状态转移方程往往与决策有着密不可分的关系（例子请参考【E.g. 03 - 数楼梯】）。 在设计状态转移方程式时，你需要包括所有可能涉及到的变量。以确保能在后续的程序实现步骤中保留所有的可能性。 步骤三：确定初始状态和边界条件 将问题分解成不能够再被分解的问题，这些问题被称之为最小问题。对于每一个最小问题，应当可以做到直接得出答案，而不需要通过计算。 例如在斐波那契数列中，所谓的最小问题就是 F(0)F(0)F(0) 和 F(1)F(1)F(1) 的值。这两个值的计算不需要依赖于任何的递推式子，而是根据定义或者逻辑直接给出的。 因此我们需要设置 F(0)F(0)F(0) 和 F(1)F(1)F(1) 的初始值，并且将这两个状态设置成边界条件。 E.G. 03 - 数楼梯 题目描述 一个楼梯有 NNN 级台阶，上楼可以一步上一阶，也可以一步上二阶。请你编写一个程序，计算走到第 NNN 级台阶共有多少种不同的走法。 解题思路 这是一道动态规划的经典例题，对于初学者而言可能对这道题目没有任何的头绪，让我们按照【解决动态规划问题的基本思路】一步一步来解决这道题。 首先确定不同的阶段，对于这道题而言，很显然不同的的阶段就是走到不同阶数的方案数，而当前楼梯的阶级就是唯一的变量。每上一层楼梯，这个变量就会增加。我们不妨定义 dpidp_idpi 表示走到第 iii 阶楼梯的方案数。 接下来确定变量和状态转移方程，在这个场景中，我们思考每一个状态之间的关联。假设我们要知道走到第十级台阶的方案数，但是我们知道想要走到第十级台阶，我们只有两个可能性（决策）： 1. 从第九级台阶迈一步走到第十级台阶。 2. 从第八级台阶迈两步走到第十级台阶。 除了这两种方法，我们没有选择。换句话说，走到某一级台阶的方案数只跟走到这之前一级和之前两级台阶的方案数有关系（无后效性），并且方案数就是这两种可能性相加的和（逻辑上也是这样子的）。用一个更宽泛的式子来描述就是： dpi=dpi−1+dpi−2\large{dp_i = dp_{i-1} + dp_{i-2}} dpi =dpi−1 +dpi−2 而这个式子就是所谓的状态转移方程式。 因此，在设计状态转移方程式的时候我们着重观察“可能性”和“决策”这两个关键点。 最后就是确定初始状态和边界条件了，根据题目要求，状态的边界条件在 1≤i≤n1\le i \le n1≤i≤n： 1. 当只有一级台阶的时候，只有一种可能性，就是从初始平台迈一步来到第一级台阶。因此 dp1=1dp_1 = 1dp1 =1。 2. 当有两级台阶的时候，有两种可能，一种是从初始平台迈两步直接来到第二级台阶，另外一种就是连续走两步走到第二级台阶。因此 dp2=2dp_2 = 2dp2 =2。 3. 到了第三级台阶，套用公式可以得到 dp3=dp1+dp2dp_3 = dp_1 + dp_2dp3 =dp1 +dp2 ，因此不再需要继续计算初始条件了。 最后，本题的 C++ 标准代码如下： E.G. 04 - 最长公共子序列 题目描述 给定两个字符串 X 和 Y，求出这两个字符串的最长公共子序列 LCS 的长度。注意，这里的子序列不要求连续，但必须保持顺序。 样例输入输出： 解题思路 这道题相比较前面的题目难度有一定的提升，我们依旧按照前文提到的基本思路来一步一步地解决这个动态规划问题。 首先来确定不同的状态（阶段），我们的目标是找出两个字符串 X 和 Y 的最长公共子序列。为了将问题分解，我们可以定义阶段和变量如下： * 阶段： 我们考察两个字符串的前缀，分别为 X[0:i] 和 Y[0:j]（即 X 的前 i 个字符和 Y 的前 j 个字符）。 * 变量： 两个变量 i 和 j 用于表示字符串 X 和 Y 的子问题范围。 在每个阶段，我们的任务是确定 X[0:i] 和 Y[0:j] 的最长公共子序列的长度。这就将整个问题分解为多个规模更小的子问题。 因此，我们考虑用 dpi,jdp_{i, j}dpi,j 来表示字符串 X[0:i] 和 Y[0:j] 的最长公共子序列的长度。 看到这里，很多人会有些许疑问（其实我当初也对这个状态的定义感到困惑，但在经过大量的实践后我发现这确实是最好的状态定义方法。事实上，我认为状态的定义在某种程度上确实是一种玄学，如果实在没有办法搞懂为什么这么定义的话就直接理解就行，不需要刨根问底。但我依然准备了几点理由）： 为什么定义阶段为 X[0:i] 和 Y[0:j]？ 原因 1：递归思想的启发 公共子序列的性质决定了大问题可以由小问题递归构建： * 假如我们已经知道了 X[0:i-1] 和 Y[0:j-1] 的最长公共子序列，那么我们可以根据 X[i-1] 和 Y[j-1] 的关系推导出 X[0:i] 和 Y[0:j] 的结果。 * 这表明，将大问题划分为较短的前缀问题是自然的。 原因 2：易于表示动态变化 通过前缀的定义，我们可以在任意时刻只关注子字符串 X[0:i] 和 Y[0:j]： * 当前阶段的解法只需要依赖之前的阶段，而不用考虑整个字符串。 * 动态规划的核心是利用阶段间的状态关系来避免重复计算，通过子问题的答案逐步推导出最终答案。 为什么选择子字符串的前缀？ 原因 1：动态规划的自底向上特性 动态规划要求我们从最小的问题开始求解，而前缀是自然的分解方式： * 对于 X[0:i] 和 Y[0:j]，最小的子问题是 i=0 或 j=0，即两个字符串中任意一个为空时，公共子序列长度为 0。 * 从空字符串到完整字符串的逐步扩展非常符合动态规划的思路。 原因 2：控制问题规模 通过逐步扩展前缀，我们可以在二维表格 dp[i][j] 中用已知的小问题结果构造更大的问题： * 如果我们随机考察 X 和 Y 的任意部分（如子序列中间），那么问题之间的关联关系会变得复杂，动态规划就难以实施。 * 而利用前缀作为阶段，每次只需要看最后一个字符的关系，并结合已有的子问题结果，问题变得简单而清晰。 接下来就到了第二步，确定状态转移方程式。通过考察字符串 X 和 Y 的最后一个字符，我们先把所有的可能性的找出来： 【情况一】当 X[i-1] == Y[j-1] 时（即两个字符串的最后一个字符相同）： 这意味着这两个字符可以成为最长公共子序列的一部分。因此，我们可以将这两个字符加入到之前计算的最长公共子序列中。因此可得 dpi,j=dpi−1,j−1dp_{i, j} = dp_{i-1, j-1}dpi,j =dpi−1,j−1 。 这里的 dp[i][j] 表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。 dp[i-1][j-1] 表示在不考虑这两个最后字符的情况下，字符串 X 的前 i-1 个字符和字符串 Y 的前 j-1 个字符的最长公共子序列的长度。由于 X[i-1] 和 Y[j-1] 相同，我们将这两个字符加入到子序列中，因此长度增加了 1。 【情况二】当 X[i-1] != Y[j-1] 时（即两个字符串的最后一个字符不同）： 由于最后一个字符不同，我们无法同时将它们加入到公共子序列中。因此，我们需要决定是排除 X 的最后一个字符还是排除 Y 的最后一个字符，以找到更长的公共子序列。因此可得 dpi,j=max⁡(dpi−1,j,dpi,j−1)dp_{i, j} = \max(dp_{i-1, j}, dp_{i, j-1})dpi,j =max(dpi−1,j ,dpi,j−1 )。 dp[i-1][j] 表示排除 X 的最后一个字符后，字符串 X 的前 i-1 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。 dp[i][j-1] 表示排除 Y 的最后一个字符后，字符串 X 的前 i 个字符和字符串 Y 的前 j-1 个字符的最长公共子序列的长度。 我们取这两者中的较大值，确保选择了能够形成最长子序列的路径。 最后就是处理边界了和初始条件了，当其中一个字符串为空时（即 i==0 || j == 0），则公共子序列的长度为零。 最后，本题的 C++ 代码如下： E.G. 05 - 最长上升子序列 题目描述 给定一个长度为 NNN 的序列 S=a1,a2,⋯ ,anS = a_1, a_2, \cdots, a_nS=a1 ,a2 ,⋯,an ，请求求出这个序列的最长上升子序列。子序列不要求连续，但每一个元素出现的顺序需要与原序列中元素出现的顺序对应。 解题思路 按照相同的方法，我们先尝试把这个大问题分解成小问题。通过观察题目，注意到长度为 NNN 的序列的最长上升子序列一定是由一个更短的序列添加一个元素得来的，因此我们只需要计算将这个元素拼接到哪一个更短的序列中可以得到一个更长的上升子序列即可。因此可以定义 dpidp_idpi 为以第 iii 个元素为结尾的最长上升子序列的长度。 接下来是状态转移方程，根据上述的定义可以得到 dpi=max⁡Sj<Si,1≤j<i(dpj+1)dp_i = \max_{S_j < S_i, 1\le j < i}(dp_j + 1)dpi =maxSj <Si ,1≤j<i (dpj +1)。该如何理解呢？ 为了计算 dpidp_idpi ，我们需要分析以 SiS_iSi 为结尾时，最长上升子序列的可能性。对于每一个 SiS_iSi ，我们需要考虑之前所有的元素（即 S1S_1S1 到 Si−1S_{i-1}Si−1 ），是否可以成为 SiS_iSi 的前驱： * 如果 Sj<SiS_j < S_iSj <Si 且 j<ij < ij<i，说明 SiS_iSi 可以接在以 SjS_jSj 为结尾的最长上升子序列后面，构成一个更大的上升子序列。 * 那么这个更大的上升子序列的长度就可以表示为： dpi=max⁡(dpj+1)，对于所有j满足Sj<Si且j<idp_i = \max(dp_j + 1)，对于所有 j 满足 S_j < S_i 且 j < i dpi =max(dpj +1)，对于所有j满足Sj <Si 且j<i 以上就是状态转移方程的推导。因此在设计状态转移方程的时候，了解并分类讨论每一个“可能性”是至关重要的。 最后就是初始值了，我们需要一开始把 dp 数组中的所有元素都设置为 111，因为无论如何，数组中的任意一个元素都可以自成一个长度为 111 的上升子序列。 最后 C++ 代码如下： E.G. 06 - 钞票问题 题目描述 Macw 在一个神奇的国家，这个国家的货币只有 111 元，555 元， 111111 元三种面值的钞票，现在 Macw 想购买一个价值为 nnn 元的物品，请问 Macw 最少需要准备多少张钞票刚好能够凑够 nnn 元？ 解题思路 这道题也是动态规划问题的经典题型。依旧按照上述动态规划“三步曲”，我们先来将问题分解出来，既然我们不知道凑够 nnn 元最少需要的钞票数量，但是与【E.g. 03 - 数楼梯】类似，我们可以将问题分解为凑够 n−1,n−2,n−3,⋯ ,1n-1, n-2, n-3, \cdots, 1n−1,n−2,n−3,⋯,1 元钱所需要的钞票数量，并从小到大来解决。因此我们定义状态 dpidp_idpi 为凑够 iii 元钱所需要的最少钞票数量。 接下来找状态转移方程，依旧寻找可能的可能性。假设我们现在有 iii 元钱，我不知道凑够 iii 元钱所需要的钞票，但是我们知道： 1. 我只需要在 i−1i- 1i−1 元钱所需要的最少面额下增加一张面额为 111 的钱即可凑到 iii 元钱。 2. 我只需要在 i−5i- 5i−5 元钱所需要的最少面额下增加一张面额为 555 的钱即可凑到 iii 元钱。 3. 我只需要在 i−11i- 11i−11 元钱所需要的最少面额下增加一张面额为 111111 的钱即可凑到 iii 元钱。 以上就是三种选择性，我们只需要找到所需钞票数量最少的那一个组合就好了，即： dpi=max⁡(dpi−1+1,dpi−5+1,dpi−11+1)\large{dp_i = \max(dp_{i-1} + 1, dp_{i-5} + 1, dp_{i-11} + 1)} dpi =max(dpi−1 +1,dpi−5 +1,dpi−11 +1) 化简可得： dpi=max⁡(dpi−1,dpi−5,dpi−11)+1\large{dp_i = \max(dp_{i-1}, dp_{i-5}, dp_{i-11}) + 1} dpi =max(dpi−1 ,dpi−5 ,dpi−11 )+1 相同地，由于一开始我们不知道凑够某一个特定面值所需要的最少钞票数量，因此我们将 dpidp_idpi 全部赋值为 ∞\infty∞。而对于 dp0dp_0dp0 我们知道凑够 000 元钱不需要任何一张钞票，因此我们特设 dp0=0dp_0 = 0dp0 =0 作为我们的初始值。 最后，我们的 C++ 代码如下： 以上就是一些基础的动态规划问题的解决方案。实际上，动态规划问题是算法和程序设计竞赛中的非常一大块内容，难度较高的动态规划问题通常与其他算法一起出现，也有许多不同的优化方法降低动态规划的时间复杂度和空间复杂度（例如线段树优化 DP、斜率优化 DP、单调队列优化 DP 等）。 我对动态规划问题学习的建议 说句实话，在我刚学习动态规划问题的时候也是一知半解，一直是一个一知半解的状态，许多题目也都是凭感觉做的。但随着刷题量越来越多，我也渐渐发现部分动态规划是有迹可循的，大部分题目都可以套类似的状态的定义和状态转移方程。毕竟动态规划这个思想本身也特别难懂，还是得需要自己去多练习才可以发现规律和找到解题技巧。 总而言之，动态规划是一种强大的算法设计方法，适用于具有最优子结构、无后效性和子问题重叠性质的问题。该思想通过将复杂问题分解为子问题，记录并重用子问题的解，动态规划能够高效地求解多阶段决策问题。理解并掌握动态规划的本质，对于解决复杂问题和优化算法性能具有重要意义。 REFERENCES GeeksforGeeks. (n.d.). Dynamic Programming. Retrieved from https://www.geeksforgeeks.org/dynamic-programming/ Gupta, R. (2023). Mastering Dynamic Programming: A Step-by-Step Guide. Medium. Retrieved from https://medium.com/@connectto.guptaraghav/mastering-dynamic-programming-a-step-by-step-guide-741d9d7d142 Stanford University. (n.d.). Dynamic Programming. Retrieved from https://web.stanford.edu/class/cs97si/04-dynamic-programming.pdf Stanford University. (2013). Dynamic Programming Lecture Notes (CS161). Retrieved from https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/16/Small16.pdf Bellman, R. (1966). Dynamic Programming. Science, 153(3731), 34–37. doi:10.1126/science.153.3731.34

32场信奥讲座#2 主讲人：黄敬文

🚀 #32场信奥讲座# 第2期 | 主讲人：黄敬文 🌟 编程界的心理压力？我们帮你轻松应对！ 🎉 本周五，加入黄敬文老师的编程情绪管理与心理健康必修课！ 👨‍🏫 黄敬文老师，将带你探索竞赛背后的情绪管理秘诀，让你在编程的世界里游刃有余！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🌈 主讲人风采 * NOI全国银牌得主，编程界的佼佼者； * 冬令营金牌，青少年编程的领军人物； ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点此了解32场硬核信奥讲座>>

信奥系列直播：大神云集，干货爆炸！

信奥系列直播：大神云集，干货爆炸，冲！ 同学们，重磅消息来啦！信奥系列直播，红头文件加持，国家认可背书，开！整！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ✨ 活动亮点 1. 阵容豪横，顶流开讲！ * 清北金牌选手：现场揭秘他们的竞赛逆袭之路！ * 顶尖教授+行业大咖：你从未听过的信奥干货就在这里！ * 教育专家坐镇：规划竞赛、选拔高校、技术提升全都有！ 2. 主题炸裂，超接地气！ * 从零到金牌：新手如何一步步走到巅峰？ * 信奥选手养成记：竞赛路上有哪些神操作？ * 双轨并行：如何平衡文化课和竞赛？ * 编程天花板：信奥大神的传奇故事了解一下！ 3. 背景太硬，机会难得！ 中国教育技术协会创客教育专业委员会主办，多家顶级机构协办，活动完全免费，你只需要点点手指报名，大神就直接送到你面前！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ✨ 讲座时间 本周五晚上19:00，准时上线，不见不散！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ✨有多牛？看官方红头文件说话！ 此次活动是为响应国家关于科技创新人才培养的战略部署，完全公益，不收取任何费用！对，你没听错！ 讲座时间：2024年11月29日到2025年7月4日，每周五晚19:00-20:30准时开播！ 锁定前排：马上扫码报名，占座超神，学到飞起！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ✨ 信奥系列直播