2026/8/5 7:13:27
FEATURED · 精选文章 
1. 项目概述与核心思路最近在带几个准备CSP-S复赛的学生集训发现他们对于动态规划和图论这两大核心模块的理解总是停留在“背模板”的阶段。一遇到稍微变化一点的题目比如把经典的“爬楼梯”问题换个场景或者在图论里加个条件就不知道怎么下手了。这让我意识到光讲理论是没用的必须用具体的、甚至看起来“简单”的题目去拆解背后的通用思维模型。就拿这个“小球落地”问题来说乍一看这跟动态规划有什么关系跟图论更是八竿子打不着。很多学生第一反应就是写个循环累加一下完事。但如果你只看到这一步那就错过了这道题真正的训练价值。在竞赛中命题人经常会把一些经典的数学模型包装成生活化、物理化的场景。你的任务就是“剥开”这层外衣看到里面那个赤裸裸的“状态转移方程”。这道题的价值在于它是一个绝佳的“思维脚手架”。它简单到足以让你看清每一个步骤但又完整地蕴含了“状态定义”、“状态转移”、“边界处理”这几个动态规划最核心的要素。同时它还可以自然地引申到“决策过程建模为图”的图论思想。我们今天的目标就是通过这个“小球”把DP和图的抽象概念变成你手里实实在在的、可复用的解题工具。我会用Python一步步实现并告诉你在赛场上遇到新题时如何快速识别并套用这种思维模式。2. 问题拆解从物理过程到数学模型我们先老老实实地把题目手算一遍这个过程至关重要它能帮你发现规律而这个规律就是状态转移方程的雏形。题目一个小球从100米高度自由落下每次落地后反弹回原高度的一半再落下。求它在第10次落地时总共经历了多少米以及第10次反弹的高度。2.1 手动模拟与规律发现我们设初始高度H 100米。第1次落地小球从100米落到地面经过路程S1 100米。落地后反弹反弹高度h1 100 / 2 50米。第2次落地小球需要从上次反弹的高度50米落下所以先经历50米落地。此时总路程S2 S1 50。落地后再次反弹反弹高度h2 50 / 2 25米。但是小球接下来还要从25米的高度再落下去为第3次落地做准备。所以从第2次落地到第3次落地之间小球其实走了“上去再下来”的过程即25 25 50米。这个路程需要计入第3次落地时的总路程。看到这里关键点就出来了从第2次落地开始每次“落地”这个事件发生时小球走过的路程都包含了“从上次反弹高度落下的路程”和“从上次落地到这次落地之间它完成的一次完整‘上升-下降’循环的路程”。更精确地说对于第i次落地i 2它首先完成了从第i-1次反弹高度h[i-1]的下降距离为h[i-1]。然后为了给第i次落地做准备在第i-1次落地后它反弹到了h[i]的高度然后又从h[i]落下。这个过程的路程是2 * h[i]。因此如果我们定义total_distance[i]第i次落地时小球经过的总路程。height[i]第i次落地后反弹的高度。那么我们可以得到初始状态height[0] H这里我们把初始高度看作第0次“反弹”高度方便计算total_distance[1] H第一次落地只经历了初始高度的下降状态转移height[i] height[i-1] / 2每次反弹高度减半total_distance[i] total_distance[i-1] height[i-1] 2 * height[i]i 2解释第i次的总路程 第i-1次的总路程 从第i-1次反弹高度落下的距离(height[i-1]) 第i次落地前完成的完整“上升-下降”路程(2 * height[i])。等等这个公式对吗我们验证一下i2。 已知total_distance[1]100,height[1]50,height[2]25。 代入total_distance[2] 100 50 2*25 200。 手动计算第一次落地100米第二次落地前小球从50米落下50米总路程150米。第二次落地后反弹到25米再落下25米为第三次落地做准备。所以到第二次落地时刻总路程确实是10050150米。我们公式算出200米显然错了。注意这里是一个经典的思维陷阱。我们混淆了“事件发生时刻”和“过程”。题目问的是“第10次落地时”这个“时”指的是落地那一瞬间。在落地瞬间小球刚刚走完“下降”过程还没有开始“上升”。所以对于第i次落地i2它只包含了从第i-1次反弹高度h[i-1]的下降过程。2.2 正确的状态定义与转移纠正后的定义total_distance[i]第i次落地瞬间小球经过的总路程。rebound_height[i]第i次落地后反弹的高度。推导第1次落地total_distance[1] H第2次落地小球走完了H第一次下降 rebound_height[1]从第一次反弹高度下降。所以total_distance[2] H rebound_height[1]。第3次落地小球走完了total_distance[2]rebound_height[2]从第二次反弹高度下降。……通用公式i 2rebound_height[i] rebound_height[i-1] / 2total_distance[i] total_distance[i-1] rebound_height[i-1]边界与初始rebound_height[0] H我们可以把初始释放点想象成“第0次反弹”的高度这样公式更统一total_distance[1] H对于i从 1 到 nn10rebound_height[i] rebound_height[i-1] / 2如果i 1:total_distance[i] H否则:total_distance[i] total_distance[i-1] rebound_height[i-1]看这就是一个清晰的动态规划模型rebound_height和total_distance就是我们的“状态”它们依赖于前一个状态并有明确的转移方程。我们成功地把一个物理问题转化为了一个可计算的递推问题。3. 动态规划DP实现与深度解析现在我们用Python来实现上述的DP思路。我会给出两种常见的DP实现方式并分析它们在竞赛中的适用场景。3.1 基础递推法自底向上这是最直观也是效率最高O(n)时间复杂度O(n)空间复杂度的实现方式。它清晰地体现了“先解决小问题再解决大问题”的DP思想。def ball_drop_dp_basic(H, n): 使用动态规划递推计算小球落地问题。 参数: H: 初始高度 (米) n: 第几次落地 (例如 10) 返回: total_distance: 第n次落地时总路程 rebound_height: 第n次落地后反弹高度 # 初始化状态数组 # rebound_height[i] 表示第i次落地后的反弹高度 rebound_height [0] * (n 1) # 多一位方便下标对齐rebound_height[0]表示初始高度 total_distance [0] * (n 1) # total_distance[i] 表示第i次落地时的总路程 # 边界条件初始化 rebound_height[0] H # 第0次“反弹”高度就是初始高度 total_distance[1] H # 第1次落地路程就是初始高度H # 状态转移递推 for i in range(1, n 1): # 计算第i次落地后的反弹高度 rebound_height[i] rebound_height[i-1] / 2.0 # 计算第i次落地时的总路程 (i1的情况已初始化) if i 1: total_distance[i] total_distance[i-1] rebound_height[i-1] return total_distance[n], rebound_height[n] # 调用函数计算第10次落地的情况 H 100.0 n 10 total_dist, rebound_h ball_drop_dp_basic(H, n) print(f【DP递推法】第{n}次落地时总路程为{total_dist:.6f} 米) print(f【DP递推法】第{n}次反弹高度为{rebound_h:.6f} 米)运行这段代码你会得到结果【DP递推法】第10次落地时总路程为299.609375 米 【DP递推法】第10次反弹高度为0.097656 米3.2 空间优化版递推滚动数组在上面的代码中我们使用了两个长度为n1的数组来存储所有状态。但仔细观察状态转移方程rebound_height[i]只依赖于rebound_height[i-1]total_distance[i]只依赖于total_distance[i-1]和rebound_height[i-1]这意味着在计算第i个状态时我们只需要前一个状态i-1的信息。因此我们可以用固定几个变量来“滚动”更新将空间复杂度从 O(n) 降低到 O(1)。这在n非常大时比如题目问第10000次落地能节省大量内存。def ball_drop_dp_optimized(H, n): 使用动态规划空间优化版计算小球落地问题。 使用滚动变量空间复杂度O(1)。 # 初始化“前一个状态” prev_rebound H # 代表 rebound_height[i-1]初始为第0次反弹高度 current_total H # 代表 total_distance[i]初始为第1次落地路程 (i1) # 如果n就是1直接返回 if n 1: return current_total, prev_rebound / 2.0 # 从第2次落地开始递推 for i in range(2, n 1): # 计算当前次落地后的反弹高度即第i次反弹高度 current_rebound prev_rebound / 2.0 # 计算当前次落地时的总路程 current_total current_total prev_rebound # total_distance[i] total_distance[i-1] rebound_height[i-1] # 更新“前一个状态”为下一次循环做准备 # 注意循环下一次要计算的是第i1次落地其需要的“前一次反弹高度”就是本次刚算出的current_rebound prev_rebound current_rebound # 循环结束后 # current_total 是 total_distance[n] # prev_rebound 是 rebound_height[n-1]不对循环内最后一步 prev_rebound current_rebound # 所以此时的 prev_rebound 是 rebound_height[n] # 但我们需要的是第n次落地后的反弹高度也就是 rebound_height[n] final_rebound prev_rebound return current_total, final_rebound # 调用验证 total_dist_opt, rebound_h_opt ball_drop_dp_optimized(H, n) print(f\n【DP空间优化法】第{n}次落地时总路程为{total_dist_opt:.6f} 米) print(f【DP空间优化法】第{n}次反弹高度为{rebound_h_opt:.6f} 米)这个版本的结果应该和基础版完全一致。在竞赛中如果题目对内存有严格要求或者n的规模极大这种优化是必须掌握的技能。3.3 动态规划思维在本问题中的映射让我们再回头审视一下这个简单的问题是如何完美体现动态规划五部曲的确定dp数组及下标的含义我们定义了两个数组rebound_height[i]和total_distance[i]下标i直接对应“第i次落地/反弹”这个阶段。这是最关键的一步定义清晰问题就解决了一半。确定递推公式我们通过分析物理过程得到了rebound_height[i] rebound_height[i-1] / 2和total_distance[i] total_distance[i-1] rebound_height[i-1]。这就是我们的“状态转移方程”。dp数组如何初始化我们明确了rebound_height[0] H和total_distance[1] H。初始化是递推的起点错了全盘皆输。确定遍历顺序由于第i个状态依赖于第i-1个状态所以我们必须从i1开始从前向后依次遍历。这是典型的“自底向上”填表法。举例推导dp数组我们在第二部分“手动模拟”就是在做这件事。动手算几步既能验证公式也能帮你发现思路中的漏洞比如我们之前犯的错误。实操心得很多同学觉得DP难是因为一上来就想写代码。我的建议是至少花一半的时间在草稿纸上完成前四步。把状态定义、转移方程、初始化和遍历顺序都想明白、写清楚代码只是水到渠成的翻译工作。这道题就是一个极好的训练强迫自己用DP的框架去思考一个看似不需要DP的问题。4. 图论视角将过程建模为有向无环图DAG如果你觉得动态规划已经够用了那可能还没触及竞赛思维的天花板。接下来我们尝试用一个更高级但也更通用的视角——图论来看待这个问题。这能帮你解决更复杂的一类“多阶段决策问题”。4.1 如何将落地过程建模成图我们把小球运动的每个“状态”抽象成图中的一个“节点”。什么是状态在这个问题里一个完整的状态可以用(落地次数, 当前高度)来表示吗不太合适因为“当前高度”在上升和下降时不同。更精妙的建模方式是将“第i次落地瞬间”和“第i次反弹到最高点瞬间”分别视为两类节点。节点L_i表示第i次落地瞬间i从1到10。属性此时的总路程S_i。节点B_i表示第i次反弹到最高点瞬间i从0到9。节点B_0就是起始点高度为H。属性此时的高度h_i。那么小球运动的过程就是在这张图上沿着有向边行走从B_0(高度H) 出发下降到L_1。这条边的“权重”就是下降的距离H它累加到L_1的总路程中。从L_1反弹到B_1(高度H/2)。这个过程虽然上升但题目只关心落地时的总路程所以这个“上升”过程的路程暂时不记录在“落地节点”上而是蕴含在后续的下降中。从B_1下降到L_2。边的权重是h_1(即H/2)。L_2的总路程 L_1的总路程 这条边的权重。从L_2反弹到B_2(高度H/4)。……以此类推直到走到节点L_10。我们发现这张图是一个简单的链状结构B_0 - L_1 - B_1 - L_2 - B_2 - ... - L_10。其中所有从B节点到L节点的边下降边有权重下降距离所有从L节点到B节点的边反弹边权重为0因为不直接贡献落地总路程。4.2 为什么说这是DAG上的动态规划我们的目标是求L_10节点的“总路程”属性。观察发现节点L_i的总路程只依赖于前驱节点L_{i-1}的总路程以及从B_{i-1}到L_i这条边的权重。节点B_i的高度只依赖于前驱节点L_i和固定的衰减规则除以2。整个图没有环是一个有向无环图DAG。在这种图上我们可以按照拓扑顺序在这里就是自然的时间顺序B_0, L_1, B_1, L_2, ...来依次计算每个节点的属性。这本质上就是动态规划每个节点的属性就是一个“状态”节点间的边定义了“状态转移”的规则和代价。4.3 Python实现显式建图与拓扑递推虽然这个问题用链式DP更简单但为了展示图论建模的思想我们可以显式地构建这个DAG并用拓扑排序的思想来求解。class Node: 图节点类 def __init__(self, node_type, index, height0.0): 初始化节点 :param node_type: B 表示反弹最高点L 表示落地瞬间 :param index: 序号 :param height: 节点对应的高度对于B节点有意义L节点可设为0 self.type node_type self.index index self.height height # B节点的高度 self.total_distance 0.0 # L节点的总路程属性 # 邻接表存储从该节点出发的边 (target_node, weight) self.edges [] def add_edge(self, target_node, weight): self.edges.append((target_node, weight)) def solve_by_graph_model(H, n): 使用图论模型DAG解决小球问题 nodes {} # 1. 构建所有节点 # 创建B0节点 nodes[B0] Node(B, 0, H) nodes[B0].total_distance 0.0 # 起始点总路程为0 for i in range(1, n 1): # 创建Li节点落地节点 nodes[fL{i}] Node(L, i, 0.0) # 创建Bi节点反弹节点其高度由前一个落地节点决定这里先创建高度稍后设置 nodes[fB{i}] Node(B, i, 0.0) # 2. 构建边并设置节点属性 # 从 B0 到 L1 的边 weight nodes[B0].height # 下降距离就是B0的高度 nodes[B0].add_edge(nodes[L1], weight) # 设置L1的总路程从B0来的权重 nodes[L1].total_distance weight for i in range(1, n): # 设置Bi的高度等于前一个反弹高度的一半B0除外 # 实际上Bi的高度 B_{i-1}.height / 2 # 但根据我们的建模Bi的高度是由Li反弹决定的而Li反弹的高度是固定的衰减关系。 # 更准确的逻辑是从Li到Bi的反弹过程决定了Bi的新高度。 # 我们在这里简化直接根据规则计算Bi的高度 prev_b_node nodes[fB{i-1}] current_b_node nodes[fB{i}] current_b_node.height prev_b_node.height / 2.0 # 添加从 Li 到 Bi 的边反弹边权重为0因为不增加总路程 nodes[fL{i}].add_edge(current_b_node, 0.0) # 添加从 Bi 到 L_{i1} 的边下降边 next_l_node nodes[fL{i1}] weight current_b_node.height current_b_node.add_edge(next_l_node, weight) # 计算 L_{i1} 的总路程 L_i的总路程 从Bi到L_{i1}的权重 nodes[fL{i}].total_distance nodes[fL{i}].total_distance # 保持不变实际上已在之前设置 next_l_node.total_distance nodes[fL{i}].total_distance weight # 处理最后一个反弹高度 Bn第n次落地后的反弹 # Bn的高度 B_{n-1}.height / 2 last_b_node nodes[fB{n}] last_b_node.height nodes[fB{n-1}].height / 2.0 # 最后一条从 Ln 到 Bn 的边虽然我们不需要用它计算路程但为了模型完整可以添加 nodes[fL{n}].add_edge(last_b_node, 0.0) # 3. 获取结果 final_total_distance nodes[fL{n}].total_distance final_rebound_height last_b_node.height return final_total_distance, final_rebound_height # 调用图论模型求解 total_dist_graph, rebound_h_graph solve_by_graph_model(H, n) print(f\n【图论模型法】第{n}次落地时总路程为{total_dist_graph:.6f} 米) print(f【图论模型法】第{n}次反弹高度为{rebound_h_graph:.6f} 米)这个实现看起来比直接的DP复杂得多但它揭示了一种强大的建模思想。对于更复杂的问题比如小球每次反弹后可能以不同的比例有时一半有时三分之一反弹或者落地时有能量损失这种状态机图模型就能轻松扩展。你可以通过修改add_edge的逻辑和节点属性的计算规则来适应新变化而DP方程可能需要重新推导。注意事项在竞赛中除非题目明显需要如状态转移非常复杂、不规则否则不建议对简单问题使用这种显式建图的方法因为它编码复杂度高。但是在思考阶段用“状态作为节点转移作为边”的图模型来梳理逻辑是破解复杂DP问题的利器。这是一种高阶的思维训练。5. 数学解析与公式直接求解对于这个特定的问题我们其实可以跳出编程思维直接找到数学上的通项公式。这不仅能验证我们程序的结果更能加深对问题本质的理解。5.1 总路程的等比数列求和让我们用数学语言重新表述 设初始高度为H。 第i次落地后的反弹高度为h_i H / (2^i)。 第i次落地瞬间的总路程为S_i。根据之前的分析S_1 HS_2 S_1 h_1 H H/2S_3 S_2 h_2 H H/2 H/4...S_n H H/2 H/4 ... H/(2^(n-1))(对于 n 1)看出来了么从第二项开始S_n是一个首项为H公比为1/2的等比数列的前n项和但注意项数H是第1项H/2是第2项...H/(2^(n-1))是第n项。所以S_n H * (1 - (1/2)^n) / (1 - 1/2) 2H * (1 - (1/2)^n)但是这个公式计算的是H H/2 ... H/(2^(n-1))的和。我们来验证一下n1:S_1 2*100*(1-0.5)100正确。n2:S_22*100*(1-0.25)150正确。因此第n次落地总路程的闭合公式为S(n) 2 * H * (1 - (1/2)^n)5.2 第n次反弹高度的公式这个更简单rebound_height(n) H / (2^n)5.3 Python实现与验证def ball_drop_math(H, n): 使用数学公式直接计算 total_distance 2 * H * (1 - (0.5) ** n) rebound_height H / (2 ** n) return total_distance, rebound_height # 调用验证 total_dist_math, rebound_h_math ball_drop_math(H, n) print(f\n【数学公式法】第{n}次落地时总路程为{total_dist_math:.6f} 米) print(f【数学公式法】第{n}次反弹高度为{rebound_h_math:.6f} 米) # 与DP结果对比验证一致性 print(f\n【一致性验证】) print(f总路程差值{abs(total_dist_math - total_dist):.10f}) print(f反弹高度差值{abs(rebound_h_math - rebound_h):.10f})数学公式法不仅代码极其简洁而且计算效率是 O(1)远高于DP的 O(n)。当n非常大时比如上亿DP循环会非常慢而公式计算依然是瞬间完成。实操心得在解决竞赛问题时养成“先寻找数学规律”的习惯。很多问题尤其是数列、递推类问题背后都有简洁的数学公式。找到它不仅能快速解题还能用于对拍验证你DP或搜索算法的正确性。当然不是所有问题都有闭合解但尝试推导一下本身就是对思维极好的锻炼。6. 代码整合、测试与扩展思考我们将几种方法整合到一个程序中并进行测试和扩展思考。6.1 完整代码示例与测试def main(): H 100.0 n 10 print(小球落地问题 - 多种解法对比) print(*50) # 解法1: 基础DP递推 total_dp, rebound_dp ball_drop_dp_basic(H, n) print(f1. 动态规划递推:) print(f 第{n}次落地总路程: {total_dp:.8f} m) print(f 第{n}次反弹高度: {rebound_dp:.8f} m) # 解法2: 空间优化DP total_opt, rebound_opt ball_drop_dp_optimized(H, n) print(f\n2. 动态规划空间优化:) print(f 第{n}次落地总路程: {total_opt:.8f} m) print(f 第{n}次反弹高度: {rebound_opt:.8f} m) print(f 与基础DP结果一致: {abs(total_opt-total_dp)1e-10 and abs(rebound_opt-rebound_dp)1e-10}) # 解法3: 图论模型 (此处调用之前定义的函数为简洁略去重复代码实际运行需包含) # total_graph, rebound_graph solve_by_graph_model(H, n) # print(f\n3. 图论模型法:) # print(f 第{n}次落地总路程: {total_graph:.8f} m) # print(f 第{n}次反弹高度: {rebound_graph:.8f} m) # 解法4: 数学公式法 total_math, rebound_math ball_drop_math(H, n) print(f\n4. 数学公式法:) print(f 第{n}次落地总路程: {total_math:.8f} m) print(f 第{n}次反弹高度: {rebound_math:.8f} m) print(f 与DP结果一致: {abs(total_math-total_dp)1e-10 and abs(rebound_math-rebound_dp)1e-10}) print(\n *50) print(f最终答案取公式法精确值:) print(f 第{n}次落地时共经过 {total_math:.6f} 米) print(f 第{n}次反弹 {rebound_math:.6f} 米高) if __name__ __main__: main()6.2 扩展思考如果问题变一下竞赛题绝不会原封不动地考你背过的题。现在我们来做几个变式训练看看如何运用刚才建立的思维模型。变式1求第10次“触地”包括落地和弹起触碰地面时总共经过的路程。注意这里“触地”包括了“落地”和“弹起后再次触地”即上升过程结束开始下降的瞬间。这相当于我们之前图模型中的每一个L节点落地和每一个从B节点下降触地的瞬间不弹起后触地就是下一次落地。仔细想“第10次触地”就是“第10次落地”。但题目如果问“前10次触地”那含义就不同了。我们按“第10次触地”就是“第10次落地”来理解那么答案不变。如果问“从开始到第10次触地包括上升和下降”那么总路程需要计算上升过程。这时每次从L_i到B_i的上升距离h_i也要计入总路程。总路程公式变为S_n H 2 * (H/2 H/4 ... H/(2^(n-1))) H 2H*(1 - (1/2)^(n-1))。你需要敏锐地捕捉这种词语差异。变式2小球每次落地后反弹高度变为上一次的k倍0k1求第n次落地总路程和反弹高度。这就是我们DP模型和图模型优势所在了。只需要修改状态转移方程中的系数DP:rebound_height[i] rebound_height[i-1] * ktotal_distance[i]的递推关系不变。数学公式S(n) H 2Hk * (1 - k^(n-1)) / (1 - k)当 k ! 1/2 时需重新推导等比数列求和 用DP实现几乎只需改动一行代码。变式3小球从高度H落下每次落地后反弹回原高度的一半再落下求它从开始到最终静止理论无限次所经过的总路程。这是一个无穷等比数列求和问题。总路程S H 2*(H/2 H/4 H/8 ...) H 2H*(1/2 1/4 1/8 ...)。括号内是一个公比为1/2的无穷等比数列其和为(1/2) / (1 - 1/2) 1。所以S H 2H*1 3H 300米。这给出了一个有趣的极限结果无论反弹多少次小球的总路程不会超过初始高度的3倍。6.3 常见错误与排查技巧在实现和调试这类问题时新手常犯以下错误循环边界错误最容易把循环次数搞错。如果从i1循环到n来计算第n次落地要清楚i代表的是当前次还是上一次。画出一个简单的状态转移表如下是避免边界错误的最佳方法。i (落地次数)反弹高度 h(i-1)总路程 S(i)计算公式1H (初始)HS(1)H2H/2H H/2S(2)S(1)h(1)3H/4H H/2 H/4S(3)S(2)h(2)变量类型错误在Python中如果H是整数如100那么H/2在Python 3中会是浮点数50.0这没问题。但如果你用了//整除或者在其他语言中如C没有注意数据类型就会得到错误结果100/250但100//250后续50//225也没问题但如果你期望小数就会出错。安全起见对于涉及除法的计算初始值建议用浮点数100.0。精度问题虽然本题对精度要求不高但要知道浮点数计算存在微小的误差。在比较两个浮点数是否相等时不要用而应该判断两者差的绝对值是否小于一个极小值如1e-10。我们的验证代码就采用了这种方法。题意理解偏差如前所述对“第10次落地时”的“时”字理解不准可能会错误地加上下一次的上升路程。务必仔细读题最好用自己的话复述一遍题意。这道“小球落地”题就像一颗棱镜。从不同角度直接模拟、DP、图论、数学公式去看会折射出不同的光彩。在CSP-S的备战中我强烈建议你多做这种“一题多解”的深度剖析。它锻炼的不是编码能力而是问题转化能力和建模能力。当你拿到一个崭新的、令人望而生畏的题目时这种能力能帮你迅速将它与你脑海中已有的模型如今天的DP状态机、DAG联系起来从而找到突破口。记住竞赛比的不是谁写的代码多而是谁能在更短的时间内看穿问题的本质。
从“小球落地”问题解析动态规划与图论建模的竞赛思维
1. 项目概述与核心思路最近在带几个准备CSP-S复赛的学生集训发现他们对于动态规划和图论这两大核心模块的理解总是停留在“背模板”的阶段。一遇到稍微变化一点的题目比如把经典的“爬楼梯”问题换个场景或者在图论里加个条件就不知道怎么下手了。这让我意识到光讲理论是没用的必须用具体的、甚至看起来“简单”的题目去拆解背后的通用思维模型。就拿这个“小球落地”问题来说乍一看这跟动态规划有什么关系跟图论更是八竿子打不着。很多学生第一反应就是写个循环累加一下完事。但如果你只看到这一步那就错过了这道题真正的训练价值。在竞赛中命题人经常会把一些经典的数学模型包装成生活化、物理化的场景。你的任务就是“剥开”这层外衣看到里面那个赤裸裸的“状态转移方程”。这道题的价值在于它是一个绝佳的“思维脚手架”。它简单到足以让你看清每一个步骤但又完整地蕴含了“状态定义”、“状态转移”、“边界处理”这几个动态规划最核心的要素。同时它还可以自然地引申到“决策过程建模为图”的图论思想。我们今天的目标就是通过这个“小球”把DP和图的抽象概念变成你手里实实在在的、可复用的解题工具。我会用Python一步步实现并告诉你在赛场上遇到新题时如何快速识别并套用这种思维模式。2. 问题拆解从物理过程到数学模型我们先老老实实地把题目手算一遍这个过程至关重要它能帮你发现规律而这个规律就是状态转移方程的雏形。题目一个小球从100米高度自由落下每次落地后反弹回原高度的一半再落下。求它在第10次落地时总共经历了多少米以及第10次反弹的高度。2.1 手动模拟与规律发现我们设初始高度H 100米。第1次落地小球从100米落到地面经过路程S1 100米。落地后反弹反弹高度h1 100 / 2 50米。第2次落地小球需要从上次反弹的高度50米落下所以先经历50米落地。此时总路程S2 S1 50。落地后再次反弹反弹高度h2 50 / 2 25米。但是小球接下来还要从25米的高度再落下去为第3次落地做准备。所以从第2次落地到第3次落地之间小球其实走了“上去再下来”的过程即25 25 50米。这个路程需要计入第3次落地时的总路程。看到这里关键点就出来了从第2次落地开始每次“落地”这个事件发生时小球走过的路程都包含了“从上次反弹高度落下的路程”和“从上次落地到这次落地之间它完成的一次完整‘上升-下降’循环的路程”。更精确地说对于第i次落地i 2它首先完成了从第i-1次反弹高度h[i-1]的下降距离为h[i-1]。然后为了给第i次落地做准备在第i-1次落地后它反弹到了h[i]的高度然后又从h[i]落下。这个过程的路程是2 * h[i]。因此如果我们定义total_distance[i]第i次落地时小球经过的总路程。height[i]第i次落地后反弹的高度。那么我们可以得到初始状态height[0] H这里我们把初始高度看作第0次“反弹”高度方便计算total_distance[1] H第一次落地只经历了初始高度的下降状态转移height[i] height[i-1] / 2每次反弹高度减半total_distance[i] total_distance[i-1] height[i-1] 2 * height[i]i 2解释第i次的总路程 第i-1次的总路程 从第i-1次反弹高度落下的距离(height[i-1]) 第i次落地前完成的完整“上升-下降”路程(2 * height[i])。等等这个公式对吗我们验证一下i2。 已知total_distance[1]100,height[1]50,height[2]25。 代入total_distance[2] 100 50 2*25 200。 手动计算第一次落地100米第二次落地前小球从50米落下50米总路程150米。第二次落地后反弹到25米再落下25米为第三次落地做准备。所以到第二次落地时刻总路程确实是10050150米。我们公式算出200米显然错了。注意这里是一个经典的思维陷阱。我们混淆了“事件发生时刻”和“过程”。题目问的是“第10次落地时”这个“时”指的是落地那一瞬间。在落地瞬间小球刚刚走完“下降”过程还没有开始“上升”。所以对于第i次落地i2它只包含了从第i-1次反弹高度h[i-1]的下降过程。2.2 正确的状态定义与转移纠正后的定义total_distance[i]第i次落地瞬间小球经过的总路程。rebound_height[i]第i次落地后反弹的高度。推导第1次落地total_distance[1] H第2次落地小球走完了H第一次下降 rebound_height[1]从第一次反弹高度下降。所以total_distance[2] H rebound_height[1]。第3次落地小球走完了total_distance[2]rebound_height[2]从第二次反弹高度下降。……通用公式i 2rebound_height[i] rebound_height[i-1] / 2total_distance[i] total_distance[i-1] rebound_height[i-1]边界与初始rebound_height[0] H我们可以把初始释放点想象成“第0次反弹”的高度这样公式更统一total_distance[1] H对于i从 1 到 nn10rebound_height[i] rebound_height[i-1] / 2如果i 1:total_distance[i] H否则:total_distance[i] total_distance[i-1] rebound_height[i-1]看这就是一个清晰的动态规划模型rebound_height和total_distance就是我们的“状态”它们依赖于前一个状态并有明确的转移方程。我们成功地把一个物理问题转化为了一个可计算的递推问题。3. 动态规划DP实现与深度解析现在我们用Python来实现上述的DP思路。我会给出两种常见的DP实现方式并分析它们在竞赛中的适用场景。3.1 基础递推法自底向上这是最直观也是效率最高O(n)时间复杂度O(n)空间复杂度的实现方式。它清晰地体现了“先解决小问题再解决大问题”的DP思想。def ball_drop_dp_basic(H, n): 使用动态规划递推计算小球落地问题。 参数: H: 初始高度 (米) n: 第几次落地 (例如 10) 返回: total_distance: 第n次落地时总路程 rebound_height: 第n次落地后反弹高度 # 初始化状态数组 # rebound_height[i] 表示第i次落地后的反弹高度 rebound_height [0] * (n 1) # 多一位方便下标对齐rebound_height[0]表示初始高度 total_distance [0] * (n 1) # total_distance[i] 表示第i次落地时的总路程 # 边界条件初始化 rebound_height[0] H # 第0次“反弹”高度就是初始高度 total_distance[1] H # 第1次落地路程就是初始高度H # 状态转移递推 for i in range(1, n 1): # 计算第i次落地后的反弹高度 rebound_height[i] rebound_height[i-1] / 2.0 # 计算第i次落地时的总路程 (i1的情况已初始化) if i 1: total_distance[i] total_distance[i-1] rebound_height[i-1] return total_distance[n], rebound_height[n] # 调用函数计算第10次落地的情况 H 100.0 n 10 total_dist, rebound_h ball_drop_dp_basic(H, n) print(f【DP递推法】第{n}次落地时总路程为{total_dist:.6f} 米) print(f【DP递推法】第{n}次反弹高度为{rebound_h:.6f} 米)运行这段代码你会得到结果【DP递推法】第10次落地时总路程为299.609375 米 【DP递推法】第10次反弹高度为0.097656 米3.2 空间优化版递推滚动数组在上面的代码中我们使用了两个长度为n1的数组来存储所有状态。但仔细观察状态转移方程rebound_height[i]只依赖于rebound_height[i-1]total_distance[i]只依赖于total_distance[i-1]和rebound_height[i-1]这意味着在计算第i个状态时我们只需要前一个状态i-1的信息。因此我们可以用固定几个变量来“滚动”更新将空间复杂度从 O(n) 降低到 O(1)。这在n非常大时比如题目问第10000次落地能节省大量内存。def ball_drop_dp_optimized(H, n): 使用动态规划空间优化版计算小球落地问题。 使用滚动变量空间复杂度O(1)。 # 初始化“前一个状态” prev_rebound H # 代表 rebound_height[i-1]初始为第0次反弹高度 current_total H # 代表 total_distance[i]初始为第1次落地路程 (i1) # 如果n就是1直接返回 if n 1: return current_total, prev_rebound / 2.0 # 从第2次落地开始递推 for i in range(2, n 1): # 计算当前次落地后的反弹高度即第i次反弹高度 current_rebound prev_rebound / 2.0 # 计算当前次落地时的总路程 current_total current_total prev_rebound # total_distance[i] total_distance[i-1] rebound_height[i-1] # 更新“前一个状态”为下一次循环做准备 # 注意循环下一次要计算的是第i1次落地其需要的“前一次反弹高度”就是本次刚算出的current_rebound prev_rebound current_rebound # 循环结束后 # current_total 是 total_distance[n] # prev_rebound 是 rebound_height[n-1]不对循环内最后一步 prev_rebound current_rebound # 所以此时的 prev_rebound 是 rebound_height[n] # 但我们需要的是第n次落地后的反弹高度也就是 rebound_height[n] final_rebound prev_rebound return current_total, final_rebound # 调用验证 total_dist_opt, rebound_h_opt ball_drop_dp_optimized(H, n) print(f\n【DP空间优化法】第{n}次落地时总路程为{total_dist_opt:.6f} 米) print(f【DP空间优化法】第{n}次反弹高度为{rebound_h_opt:.6f} 米)这个版本的结果应该和基础版完全一致。在竞赛中如果题目对内存有严格要求或者n的规模极大这种优化是必须掌握的技能。3.3 动态规划思维在本问题中的映射让我们再回头审视一下这个简单的问题是如何完美体现动态规划五部曲的确定dp数组及下标的含义我们定义了两个数组rebound_height[i]和total_distance[i]下标i直接对应“第i次落地/反弹”这个阶段。这是最关键的一步定义清晰问题就解决了一半。确定递推公式我们通过分析物理过程得到了rebound_height[i] rebound_height[i-1] / 2和total_distance[i] total_distance[i-1] rebound_height[i-1]。这就是我们的“状态转移方程”。dp数组如何初始化我们明确了rebound_height[0] H和total_distance[1] H。初始化是递推的起点错了全盘皆输。确定遍历顺序由于第i个状态依赖于第i-1个状态所以我们必须从i1开始从前向后依次遍历。这是典型的“自底向上”填表法。举例推导dp数组我们在第二部分“手动模拟”就是在做这件事。动手算几步既能验证公式也能帮你发现思路中的漏洞比如我们之前犯的错误。实操心得很多同学觉得DP难是因为一上来就想写代码。我的建议是至少花一半的时间在草稿纸上完成前四步。把状态定义、转移方程、初始化和遍历顺序都想明白、写清楚代码只是水到渠成的翻译工作。这道题就是一个极好的训练强迫自己用DP的框架去思考一个看似不需要DP的问题。4. 图论视角将过程建模为有向无环图DAG如果你觉得动态规划已经够用了那可能还没触及竞赛思维的天花板。接下来我们尝试用一个更高级但也更通用的视角——图论来看待这个问题。这能帮你解决更复杂的一类“多阶段决策问题”。4.1 如何将落地过程建模成图我们把小球运动的每个“状态”抽象成图中的一个“节点”。什么是状态在这个问题里一个完整的状态可以用(落地次数, 当前高度)来表示吗不太合适因为“当前高度”在上升和下降时不同。更精妙的建模方式是将“第i次落地瞬间”和“第i次反弹到最高点瞬间”分别视为两类节点。节点L_i表示第i次落地瞬间i从1到10。属性此时的总路程S_i。节点B_i表示第i次反弹到最高点瞬间i从0到9。节点B_0就是起始点高度为H。属性此时的高度h_i。那么小球运动的过程就是在这张图上沿着有向边行走从B_0(高度H) 出发下降到L_1。这条边的“权重”就是下降的距离H它累加到L_1的总路程中。从L_1反弹到B_1(高度H/2)。这个过程虽然上升但题目只关心落地时的总路程所以这个“上升”过程的路程暂时不记录在“落地节点”上而是蕴含在后续的下降中。从B_1下降到L_2。边的权重是h_1(即H/2)。L_2的总路程 L_1的总路程 这条边的权重。从L_2反弹到B_2(高度H/4)。……以此类推直到走到节点L_10。我们发现这张图是一个简单的链状结构B_0 - L_1 - B_1 - L_2 - B_2 - ... - L_10。其中所有从B节点到L节点的边下降边有权重下降距离所有从L节点到B节点的边反弹边权重为0因为不直接贡献落地总路程。4.2 为什么说这是DAG上的动态规划我们的目标是求L_10节点的“总路程”属性。观察发现节点L_i的总路程只依赖于前驱节点L_{i-1}的总路程以及从B_{i-1}到L_i这条边的权重。节点B_i的高度只依赖于前驱节点L_i和固定的衰减规则除以2。整个图没有环是一个有向无环图DAG。在这种图上我们可以按照拓扑顺序在这里就是自然的时间顺序B_0, L_1, B_1, L_2, ...来依次计算每个节点的属性。这本质上就是动态规划每个节点的属性就是一个“状态”节点间的边定义了“状态转移”的规则和代价。4.3 Python实现显式建图与拓扑递推虽然这个问题用链式DP更简单但为了展示图论建模的思想我们可以显式地构建这个DAG并用拓扑排序的思想来求解。class Node: 图节点类 def __init__(self, node_type, index, height0.0): 初始化节点 :param node_type: B 表示反弹最高点L 表示落地瞬间 :param index: 序号 :param height: 节点对应的高度对于B节点有意义L节点可设为0 self.type node_type self.index index self.height height # B节点的高度 self.total_distance 0.0 # L节点的总路程属性 # 邻接表存储从该节点出发的边 (target_node, weight) self.edges [] def add_edge(self, target_node, weight): self.edges.append((target_node, weight)) def solve_by_graph_model(H, n): 使用图论模型DAG解决小球问题 nodes {} # 1. 构建所有节点 # 创建B0节点 nodes[B0] Node(B, 0, H) nodes[B0].total_distance 0.0 # 起始点总路程为0 for i in range(1, n 1): # 创建Li节点落地节点 nodes[fL{i}] Node(L, i, 0.0) # 创建Bi节点反弹节点其高度由前一个落地节点决定这里先创建高度稍后设置 nodes[fB{i}] Node(B, i, 0.0) # 2. 构建边并设置节点属性 # 从 B0 到 L1 的边 weight nodes[B0].height # 下降距离就是B0的高度 nodes[B0].add_edge(nodes[L1], weight) # 设置L1的总路程从B0来的权重 nodes[L1].total_distance weight for i in range(1, n): # 设置Bi的高度等于前一个反弹高度的一半B0除外 # 实际上Bi的高度 B_{i-1}.height / 2 # 但根据我们的建模Bi的高度是由Li反弹决定的而Li反弹的高度是固定的衰减关系。 # 更准确的逻辑是从Li到Bi的反弹过程决定了Bi的新高度。 # 我们在这里简化直接根据规则计算Bi的高度 prev_b_node nodes[fB{i-1}] current_b_node nodes[fB{i}] current_b_node.height prev_b_node.height / 2.0 # 添加从 Li 到 Bi 的边反弹边权重为0因为不增加总路程 nodes[fL{i}].add_edge(current_b_node, 0.0) # 添加从 Bi 到 L_{i1} 的边下降边 next_l_node nodes[fL{i1}] weight current_b_node.height current_b_node.add_edge(next_l_node, weight) # 计算 L_{i1} 的总路程 L_i的总路程 从Bi到L_{i1}的权重 nodes[fL{i}].total_distance nodes[fL{i}].total_distance # 保持不变实际上已在之前设置 next_l_node.total_distance nodes[fL{i}].total_distance weight # 处理最后一个反弹高度 Bn第n次落地后的反弹 # Bn的高度 B_{n-1}.height / 2 last_b_node nodes[fB{n}] last_b_node.height nodes[fB{n-1}].height / 2.0 # 最后一条从 Ln 到 Bn 的边虽然我们不需要用它计算路程但为了模型完整可以添加 nodes[fL{n}].add_edge(last_b_node, 0.0) # 3. 获取结果 final_total_distance nodes[fL{n}].total_distance final_rebound_height last_b_node.height return final_total_distance, final_rebound_height # 调用图论模型求解 total_dist_graph, rebound_h_graph solve_by_graph_model(H, n) print(f\n【图论模型法】第{n}次落地时总路程为{total_dist_graph:.6f} 米) print(f【图论模型法】第{n}次反弹高度为{rebound_h_graph:.6f} 米)这个实现看起来比直接的DP复杂得多但它揭示了一种强大的建模思想。对于更复杂的问题比如小球每次反弹后可能以不同的比例有时一半有时三分之一反弹或者落地时有能量损失这种状态机图模型就能轻松扩展。你可以通过修改add_edge的逻辑和节点属性的计算规则来适应新变化而DP方程可能需要重新推导。注意事项在竞赛中除非题目明显需要如状态转移非常复杂、不规则否则不建议对简单问题使用这种显式建图的方法因为它编码复杂度高。但是在思考阶段用“状态作为节点转移作为边”的图模型来梳理逻辑是破解复杂DP问题的利器。这是一种高阶的思维训练。5. 数学解析与公式直接求解对于这个特定的问题我们其实可以跳出编程思维直接找到数学上的通项公式。这不仅能验证我们程序的结果更能加深对问题本质的理解。5.1 总路程的等比数列求和让我们用数学语言重新表述 设初始高度为H。 第i次落地后的反弹高度为h_i H / (2^i)。 第i次落地瞬间的总路程为S_i。根据之前的分析S_1 HS_2 S_1 h_1 H H/2S_3 S_2 h_2 H H/2 H/4...S_n H H/2 H/4 ... H/(2^(n-1))(对于 n 1)看出来了么从第二项开始S_n是一个首项为H公比为1/2的等比数列的前n项和但注意项数H是第1项H/2是第2项...H/(2^(n-1))是第n项。所以S_n H * (1 - (1/2)^n) / (1 - 1/2) 2H * (1 - (1/2)^n)但是这个公式计算的是H H/2 ... H/(2^(n-1))的和。我们来验证一下n1:S_1 2*100*(1-0.5)100正确。n2:S_22*100*(1-0.25)150正确。因此第n次落地总路程的闭合公式为S(n) 2 * H * (1 - (1/2)^n)5.2 第n次反弹高度的公式这个更简单rebound_height(n) H / (2^n)5.3 Python实现与验证def ball_drop_math(H, n): 使用数学公式直接计算 total_distance 2 * H * (1 - (0.5) ** n) rebound_height H / (2 ** n) return total_distance, rebound_height # 调用验证 total_dist_math, rebound_h_math ball_drop_math(H, n) print(f\n【数学公式法】第{n}次落地时总路程为{total_dist_math:.6f} 米) print(f【数学公式法】第{n}次反弹高度为{rebound_h_math:.6f} 米) # 与DP结果对比验证一致性 print(f\n【一致性验证】) print(f总路程差值{abs(total_dist_math - total_dist):.10f}) print(f反弹高度差值{abs(rebound_h_math - rebound_h):.10f})数学公式法不仅代码极其简洁而且计算效率是 O(1)远高于DP的 O(n)。当n非常大时比如上亿DP循环会非常慢而公式计算依然是瞬间完成。实操心得在解决竞赛问题时养成“先寻找数学规律”的习惯。很多问题尤其是数列、递推类问题背后都有简洁的数学公式。找到它不仅能快速解题还能用于对拍验证你DP或搜索算法的正确性。当然不是所有问题都有闭合解但尝试推导一下本身就是对思维极好的锻炼。6. 代码整合、测试与扩展思考我们将几种方法整合到一个程序中并进行测试和扩展思考。6.1 完整代码示例与测试def main(): H 100.0 n 10 print(小球落地问题 - 多种解法对比) print(*50) # 解法1: 基础DP递推 total_dp, rebound_dp ball_drop_dp_basic(H, n) print(f1. 动态规划递推:) print(f 第{n}次落地总路程: {total_dp:.8f} m) print(f 第{n}次反弹高度: {rebound_dp:.8f} m) # 解法2: 空间优化DP total_opt, rebound_opt ball_drop_dp_optimized(H, n) print(f\n2. 动态规划空间优化:) print(f 第{n}次落地总路程: {total_opt:.8f} m) print(f 第{n}次反弹高度: {rebound_opt:.8f} m) print(f 与基础DP结果一致: {abs(total_opt-total_dp)1e-10 and abs(rebound_opt-rebound_dp)1e-10}) # 解法3: 图论模型 (此处调用之前定义的函数为简洁略去重复代码实际运行需包含) # total_graph, rebound_graph solve_by_graph_model(H, n) # print(f\n3. 图论模型法:) # print(f 第{n}次落地总路程: {total_graph:.8f} m) # print(f 第{n}次反弹高度: {rebound_graph:.8f} m) # 解法4: 数学公式法 total_math, rebound_math ball_drop_math(H, n) print(f\n4. 数学公式法:) print(f 第{n}次落地总路程: {total_math:.8f} m) print(f 第{n}次反弹高度: {rebound_math:.8f} m) print(f 与DP结果一致: {abs(total_math-total_dp)1e-10 and abs(rebound_math-rebound_dp)1e-10}) print(\n *50) print(f最终答案取公式法精确值:) print(f 第{n}次落地时共经过 {total_math:.6f} 米) print(f 第{n}次反弹 {rebound_math:.6f} 米高) if __name__ __main__: main()6.2 扩展思考如果问题变一下竞赛题绝不会原封不动地考你背过的题。现在我们来做几个变式训练看看如何运用刚才建立的思维模型。变式1求第10次“触地”包括落地和弹起触碰地面时总共经过的路程。注意这里“触地”包括了“落地”和“弹起后再次触地”即上升过程结束开始下降的瞬间。这相当于我们之前图模型中的每一个L节点落地和每一个从B节点下降触地的瞬间不弹起后触地就是下一次落地。仔细想“第10次触地”就是“第10次落地”。但题目如果问“前10次触地”那含义就不同了。我们按“第10次触地”就是“第10次落地”来理解那么答案不变。如果问“从开始到第10次触地包括上升和下降”那么总路程需要计算上升过程。这时每次从L_i到B_i的上升距离h_i也要计入总路程。总路程公式变为S_n H 2 * (H/2 H/4 ... H/(2^(n-1))) H 2H*(1 - (1/2)^(n-1))。你需要敏锐地捕捉这种词语差异。变式2小球每次落地后反弹高度变为上一次的k倍0k1求第n次落地总路程和反弹高度。这就是我们DP模型和图模型优势所在了。只需要修改状态转移方程中的系数DP:rebound_height[i] rebound_height[i-1] * ktotal_distance[i]的递推关系不变。数学公式S(n) H 2Hk * (1 - k^(n-1)) / (1 - k)当 k ! 1/2 时需重新推导等比数列求和 用DP实现几乎只需改动一行代码。变式3小球从高度H落下每次落地后反弹回原高度的一半再落下求它从开始到最终静止理论无限次所经过的总路程。这是一个无穷等比数列求和问题。总路程S H 2*(H/2 H/4 H/8 ...) H 2H*(1/2 1/4 1/8 ...)。括号内是一个公比为1/2的无穷等比数列其和为(1/2) / (1 - 1/2) 1。所以S H 2H*1 3H 300米。这给出了一个有趣的极限结果无论反弹多少次小球的总路程不会超过初始高度的3倍。6.3 常见错误与排查技巧在实现和调试这类问题时新手常犯以下错误循环边界错误最容易把循环次数搞错。如果从i1循环到n来计算第n次落地要清楚i代表的是当前次还是上一次。画出一个简单的状态转移表如下是避免边界错误的最佳方法。i (落地次数)反弹高度 h(i-1)总路程 S(i)计算公式1H (初始)HS(1)H2H/2H H/2S(2)S(1)h(1)3H/4H H/2 H/4S(3)S(2)h(2)变量类型错误在Python中如果H是整数如100那么H/2在Python 3中会是浮点数50.0这没问题。但如果你用了//整除或者在其他语言中如C没有注意数据类型就会得到错误结果100/250但100//250后续50//225也没问题但如果你期望小数就会出错。安全起见对于涉及除法的计算初始值建议用浮点数100.0。精度问题虽然本题对精度要求不高但要知道浮点数计算存在微小的误差。在比较两个浮点数是否相等时不要用而应该判断两者差的绝对值是否小于一个极小值如1e-10。我们的验证代码就采用了这种方法。题意理解偏差如前所述对“第10次落地时”的“时”字理解不准可能会错误地加上下一次的上升路程。务必仔细读题最好用自己的话复述一遍题意。这道“小球落地”题就像一颗棱镜。从不同角度直接模拟、DP、图论、数学公式去看会折射出不同的光彩。在CSP-S的备战中我强烈建议你多做这种“一题多解”的深度剖析。它锻炼的不是编码能力而是问题转化能力和建模能力。当你拿到一个崭新的、令人望而生畏的题目时这种能力能帮你迅速将它与你脑海中已有的模型如今天的DP状态机、DAG联系起来从而找到突破口。记住竞赛比的不是谁写的代码多而是谁能在更短的时间内看穿问题的本质。 
