题意分析 这是一道经典的水题线性动态规划问题，是 A93766A93766A93766 的拓展，每次可以选择走 sss 步（1≤s≤k1\leq s\leq k1≤s≤k），求到终点的最小代价。 解题思路 我们先要知道，动态规划的根本——子问题是什么，即 dpidp_idpi 应该表示什么。 要跳到任何一块石阶上，青蛙只有 kkk 种跳法，从前 kkk 块石阶跳过来。因此我们可以发现，跳到这一块石阶的最小花费，即 dpidp_idpi ，是由前 kkk 块台阶转移而来的。青蛙不用动就已经在第一块石阶上，因此 dp1dp_1dp1 为 000。青蛙只能从第一块石阶跳到第二块石阶上，因此 dp2dp_2dp2 为第一、二块石阶的高度差。接下来，根据这些信息就可以得知第三块、第四块、第五块…… AC代码 时间复杂度 O(n×k)O(n\times k)O(n×k)，可以接受。

本题几乎与93766一模一样，因此只给出转移方程和代码，剩下可以查看93766题解理解 设 dpidp_idpi 为跳到第 iii 石头时的最小花费。 可以轻易发现，本题的转移方程为： dpi=min⁡(dpi,dpi−j+abs(a[i]−a[i−j]))其中j∈[1,min⁡(m,i−m−1)]dp_i = \min(dp_i , dp_{i - j} + \text{abs}(a[i] - a[i-j])) \text{其中} j \in [1,\min(m , i - m - 1)] dpi =min(dpi ,dpi−j +abs(a[i]−a[i−j]))其中j∈[1,min(m,i−m−1)] 代码如下：