题解 AT4522 【Frog 1】

Zirnc · 2020-02-15 12:03:12 · 题解

ChungZH's blog · ChungZH's portfolio

这是一道简单的线性动态规划 dp 题。

第 i 个石头只能从第 i-1 个石头或者第 i-2 个石头跳过去。

设 dp_i 为青蛙到第 i 块石头的最小代价，那么 dp_i = min(dp_{i-2} + abs(h_i - h_{i - 2}), dp_{i-1} + abs(h_i - h_{i-1}))。

注意：dp_1 = 0, dp_2 = |h_2-h_1|。

核心代码：

  dp[1] = 0;
  dp[2] = abs(h[2] - h[1]);
  for (int i = 3; i <= n; i++) {
    dp[i] =
        min(dp[i - 2] + abs(h[i] - h[i - 2]), dp[i - 1] + abs(h[i] - h[i - 1]));
  }