题意分析 这是一道经典的线性动态规划问题，每次选择走一步或两步，求到终点的最小代价。 解题思路 我们先要知道，动态规划的根本——子问题该选择什么，即 dpidp_idpi 应该表示什么。先来分析一个最简单的问题： 要跳到任何一块石阶上，青蛙只有两种跳法，从上上块石阶直接跳过来，或者从上一块石阶跳过来。因此我们可以发现，如果可以知道跳到上一块与上上块石阶的最小花费，就可以知道跳到这一块石阶的最小花费。那有没有什么可以确定的条件呢？青蛙不用动就已经在第一块石阶上，因此 dp1dp_1dp1 为 000。青蛙只能从第一块石阶跳到第二块石阶上，因此 dp2dp_2dp2 为第一、二块石阶的高度差。接下来，根据这些信息就可以得知第三块、第四块、第五块…… AC代码 滚动数组优化 时间复杂度 O(n)O(n)O(n)，看到上一篇题解，我也要吐槽下了，橙题都要用 AIAIAI 还不抓紧了学，直接复制连思路都不了解下那还打什么竞赛。

吐槽 怎么管的这么怂，3个人代码里（除了我）2个AI，1个复制别人的AI代码。 题目大意 给你n块石头，每次跳跃跳下一个或者空一格，跳一次的代价是 abs(ai−aj)\text{abs}(a_i - a_j)abs(ai −aj ) 其中 i,ji,ji,j 分别指起点位置和重点位置。要求你求出跳到第 nnn 块石头的最小代价。 思路 本题考虑dp。 设 dpidp_idpi 为跳到第 iii 块石头的最小值。同时我们发现，想到达第 iii 石头，必须从 i−1i - 1i−1 或 i−2i - 2i−2到达。因此 dpidp_idpi 的值也一定只由 dpi−1,dpi−2dp_{i - 1} , dp_{i - 2}dpi−1 ,dpi−2 决定。很快我们就能发现转移方程： dpi=min⁡(dpi−1+abs(ai−ai−1),dpi−2+abs(ai−ai−2))dp_i = \min(dp_{i - 1} + \text{abs}(a_i - a_{i - 1}) , dp_{i - 2} + \text{abs}(a_i - a_{i - 2})) dpi =min(dpi−1 +abs(ai −ai−1 ),dpi−2 +abs(ai −ai−2 )) 最后输出 dpndp_ndpn 即可。 当然可以使用滚动数组（不给代码自己写）。