题目链接 收集金币 题目描述 在一个  的网格迷宫中，每个方格  都有一定数量的金币。小K从左上角  出发，每回合只能向右或向下移动一格。 迷宫中存在动态障碍：已知有  条信息，每条信息形如 ，表示方格  会在第  回合开始时永久变成墙。 小K的目标是规划一条路径，使得收集到的金币总数最多。一个方格中的金币只能被收集一次。 解题思路 这是一个带有时间限制的路径规划问题，是经典网格动态规划的变种。 1. 关键点：回合数与坐标的关系 小K从  出发，每回合移动一格。要想到达方格 ，必须经过  次向下移动和  次向右移动，总共移动  次。 这意味着，小K 到达 方格  的时刻（即完成的移动回合数）恰...

题目链接 [小红删数字]https://www.nowcoder.com/practice/a246d1e2b38e454985ac1400591d6175 题目描述 给定一个长度为  的整数数组 。需要进行恰好  次操作，直到数组中只剩下一个数字。 每次操作固定地针对当前数组的最后两个数 （ 在前， 在后）进行，并二选一执行：  将  删除，并将  的结果插入到数组末尾。 将  删除，并将  的结果插入到数组末尾。  请统计在所有可能的操作序列下（即每次操作的两种选择），最终结果为  的方案数各有多少。答案需要对  取模。 解题思路 1. 分析操作结构 操作的顺序是固定的，总是从数组的末尾开...

题目链接 我不是大富翁 题目描述 在一张有  个地块的环形大富翁地图上，地块从  到  顺时针编号。游戏开始时，玩家位于  号地块。 游戏共进行  个回合。在一个长度为  的行动力序列  中，第  回合的行动力为 。在每个回合，玩家可以自由选择移动方向（顺时针或逆时针），并移动  个地块。 问题是：是否存在一种移动方式，使得在  个回合结束后，玩家能恰好回到  号地块。 解题思路 本题的核心是判断经过一系列操作后，能否到达一个特定的状态。这是一个经典的可达性问题，非常适合使用动态规划来解决。 问题的关键在于，在第  回合，如果我们当前的位置是 ，行动力是 ，我们可以移动到  或者 。我们不需要...

题目链接 能量项链 题目描述 在一个环形的项链上，有  颗能量珠。每颗珠子  有一个头标记  和一个尾标记 。相邻的两颗珠子  和 （其中 ）可以合并，释放出  的能量，并形成一颗头标记为 、尾标记为  的新珠子。要求找出一种合并顺序，将所有珠子合并为一颗，使得释放的总能量最大。 输入数据为  个头标记，其中第  颗珠子的尾标记等于第  颗珠子的头标记（第  颗的尾标记等于第 1 颗的头标记）。 解题思路 本题是区间动态规划（Interval DP）在环形结构上的一个典型应用，与经典的矩阵链乘问题非常相似。 1. 问题转化：处理环形结构 环形结构给 DP 带来了困难，因为没有固定的起点和终点。...

题目描述 给定一个长度为  的 01 串 ，以及两个整数参数  和 。我们可以对任意一个长度大于等于2的子串进行“切割”操作。 一次合法的切割操作定义如下：  选择一个子串，将其分成两个非空的连续子串 （左）和 （右）。 记  中字符 '0' 的出现次数为 ， 中字符 '1' 的出现次数为 。 当且仅当  时，此次切割是合法的。  每次合法切割后产生的两个新子串，如果长度仍然大于等于2，可以被独立地继续进行切割。问题是，在最优策略下，最多可以执行多少次切割操作。 解题思路 这是一个典型的区间动态规划问题。问题的最优解包含其子问题的最优解（最优子结构），且子问题会被重复计算（重叠子问题），这完全...

题目描述 给定一个包含  个生物和  条捕食关系的食物网，这可以被看作一个有向无环图 (DAG)。每条有向边由一对整数  表示：生物  捕食生物 ，形成一条有向边 。 题目对“食物链”的定义如下：  起点是生产者：不会捕食其它生物，即在图中出度为 0 的节点。 终点是顶级消费者：不会被其它生物捕食，即在图中入度为 0 的节点。 路径需要沿有向边（捕食方向）从起点连接到终点。  题目保证最终答案不超过 。 解题思路 1. 题意分析 题目的描述存在一个核心的逻辑矛盾：食物链的起点被定义为“出度为0”的节点，但路径又必须“沿有向边方向”进行。一个出度为0的节点没有任何出边，因此不可能沿有向边到达任何...

题目链接 石子合并 题目描述 有  堆石子排成一行，第  堆石子的质量为 。每次操作只能选择相邻的两堆石子合并，代价等于这两堆石子的质量之和。合并后形成的新石堆质量也为两者之和，并继续与左右相邻石堆相邻。目标是找到一种合并顺序，使得将所有石子合并成一堆的总代价最小。 解题思路 这是一个典型的区间动态规划问题。我们的目标是求将所有  堆石子合并为一堆的最小代价。 1. 状态定义 我们定义  为将区间 （即从第  堆到第  堆）的石子合并成一堆的最小代价。我们的最终目标是求解 。 2. 状态转移 对于区间 ，其最后一次合并必然是将两个已经合并好的相邻子区间合并而成的。我们可以枚举这个分割点 ，其中...

HIGH93 没有上司的舞会 题目描述 公司准备举办一场晚会，共有  名员工。每名员工都有一个“气氛值”，邀请他们可以为晚会增加对应的气氛值。 规则是：如果邀请了一名员工，那么他的直接上司就不能被邀请。 已知公司的层级关系是一棵树，根节点是老板。请求出一个邀请方案，使得晚会的总气氛值最大。 解题思路 这是一个经典的树形动态规划问题，通常被称为“没有上司的舞会”。核心约束是：一个节点和它的父节点不能同时被选择。 1. 模型抽象  图结构: 公司的组织架构是一棵树。我们需要先根据输入的上下级关系建树，并找到树的根节点（没有上司的员工）。 决策: 对于每个员工（树中的节点），我们都有两种决策：邀请他...

HIGH92 最大学分 题目描述 在大学选课系统中，共有  门课程，需要从中选出恰好  门。每门课程  有  的学分和至多一门直接先修课 。 选课必须满足先修课约束，即要选修一门课程，必须先选修它的直接先修课，以及先修课的先修课，以此类推，直到根课程（没有先修课的课程）。 请求出在满足约束的条件下，选修  门课程能获得的最大总学分。 解题思路 这是一个在树形依赖结构上进行选择，以在限定数量下最大化价值的问题。这是一个经典的树形背包（或称树形DP）问题。 1. 模型抽象  图结构: 课程之间的先修关系构成了一个森林（由多棵树组成）。每门没有先修课的课程（）是其所在树的根节点。 依赖关系: “选一...

HIGH91 来硬的 题目描述 共有  枚煤炭和  单位的铁矿石。第  枚煤炭可以融化  单位的铁矿石，燃烧时间为  秒。 你拥有一项魔法，最多可以对一枚煤炭施放，将其升级。若第  枚煤炭被升级，它将可以融化  单位的矿石，而燃烧时间缩短为  秒。 熔炉同一时刻只能燃烧一枚燃料。请求出将所有  单位铁矿石全部烧炼完毕，所需要的最短总时间。 解题思路 这是一个在满足特定“价值”（融化量）要求下，最小化“成本”（燃烧时间）的问题，是典型的背包问题变种。然而，由于单个煤炭的融化量  可能非常大，直接以融化量为维度的DP数组会导致内存溢出。 正确的思路是基于数据范围进行分类讨论和剪枝。任何最优解，要么...

HIGH90 小红笔试 题目描述 小红参加一场有  道题的编程笔试，总时长为  分钟。对于第  道题，她有三种选择：  写出正确算法：耗时 ，得分 。 写出暴力算法：耗时 ，得分 。 放弃此题：耗时 ，得分 。  要求规划一个做题方案，使得在总耗时不超过  的前提下，总得分最大。并输出这个方案。 解题思路 这是一个典型的分组背包问题。我们可以将总时长  视作背包的容量，每道题的得分视作物品的价值，做题耗时视作物品的重量。 1. 模型抽象  背包容量：总时长 。 物品组：共  个组，每道题构成一个独立的组。 组内物品：对于第  道题（第  组），组内有三个互斥的“物品”可供选择，分别对应三种策略...

HIGH89 【模板】分组背包 题目描述 给定  件物品与一只最大可承重为  的背包。所有物品被划分为若干个组，同一组中的物品是互斥的：对于每个组，你最多只能选择其中的一件物品。 第  件物品的重量是 ，价值是 ，所属组别为 。 请你在不超过背包承重  的前提下，选择若干物品使得总价值最大。 解题思路 这是一个经典的分组背包问题。它的特点是物品被分成了若干组，每组内的物品相互冲突，最多只能选择一个。 分组背包可以看作是0-1背包的一种扩展。在0-1背包中，我们对每个物品做决策：选或不选。在分组背包中，我们的决策单位变成了“组”：对于每一组，我们的决策是：  不选择该组中的任何物品。 选择该组中...

HIGH88 【模板】二维费用背包 题目描述 小红有  个事件可以分享。她希望在总耗时不超过 ，总消耗精力不超过  的前提下，选择若干事件进行分享，使得收获的快乐值总和最大。 对于第  个事件，若要发布，需要耗费  分钟时间与  点精力，并能让她获得  点快乐值。每个事件最多只能选择一次。 解题思路 这是一个经典的二维费用背包问题。它本质上是一个0-1背包问题，但每个物品有两个不同的“费用”（或“体积”），这里分别是时间和精力。我们需要在这两个限制条件下，最大化总“价值”（快乐值）。 1. 状态定义 由于有两个费用维度，我们的动态规划状态也需要是二维的。 我们定义一个二维数组 ， 的含义是：在...

HIGH87 【模板】多重背包 题目描述 有  种物品和一个容量为  的背包。第  种物品的体积是 ，价值是 ，并且数量最多有  件。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 解题思路 这是一个经典的多重背包问题。它介于0-1背包（每种物品只有1件）和完全背包（每种物品有无限件）之间。 最朴素的想法是将第  种物品看作  件独立的、体积为 、价值为  的物品，然后直接套用0-1背包的解法。但这种方法在  很大时，总物品数量会急剧增加，导致超时。 更高效的策略是二进制优化（也称二进制拆分），其核心思想是将多重背包问题转化为一个等价的0-1背包问题，同时控制转化...