背景

Frog 1 的进阶版，将固定跳跃步数改成了动态步数。核心思路不变，但多了初始化细节。

思路分析

定义 dp[i] 为跳到第 i 个石头的最小花费。

每次可以从第 i 个石头跳到 i+1 到 i+k 范围内的任意石头：

1
dp[i + j] = min(dp[i + j], dp[i] + |a[i] - a[i + j]|)

关键细节：因为取的是最小值，而 int[] 默认值为 0，需要先初始化成极大值，同时 dp[1] = 0（从起点开始，花费为 0）。

代码实现

1
2
3
4
5
6
7
8
9
10
11
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) dp[i] = Integer.MAX_VALUE;
dp[1] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
        if (i + j <= n)
            dp[i + j] = Math.min(dp[i + j], dp[i] + Math.abs(a[i] - a[i + j]));
        else break;
    }
}
System.out.println(dp[n]);

小结

  • 线性 DP，但步数不固定，加一层循环即可
  • 注意初始化：取最小值时一定要把 dp 初始化为极大值，否则默认的 0 会干扰结果