题解 AT4522 【Frog 1】
Zirnc
2020-02-15 12:03:12
[ChungZH's blog](https://chungzh.cn) · [ChungZH's portfolio](https://chungzh.cc)
这是一道简单的线性动态规划 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|$。
核心代码：
```cpp
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]));
}
```