01_Introduction to DP 动态规划简介

动态规划简介

核心思想

将大问题拆解为小问题，记录子问题的解，避免重复计算。

---

示例 - 青蛙 1 (Frog 1)

题目描述

题目要求我们计算青蛙从石头 1 跳到石头 N (N ≤ 10⁵) 的最小总成本，已知青蛙只能跳一或两的距离。任意两个石头 i 和 j 之间的旅行成本由 |h_i − h_j| 给出，其中 h_i 表示石头 i 的高度。

---

解法

拉动态规划 (Pull DP) - 常用

定义 dp[i] 为到达石头 i 的最小成本。

状态转移： - 从 i-1 跳来：dp[i] = min(dp[i], dp[i-1] + |h[i] - h[i-1]|) - 从 i-2 跳来：dp[i] = min(dp[i], dp[i-2] + |h[i] - h[i-2]|)

N = int(input())
height = [int(s) for s in input().split()]

dp = [float("inf")] * N
dp[0] = 0

for i in range(1, N):
    if i - 1 >= 0:
        dp[i] = min(dp[i], dp[i-1] + abs(height[i] - height[i-1]))
    if i - 2 >= 0:
        dp[i] = min(dp[i], dp[i-2] + abs(height[i] - height[i-2]))

print(dp[N-1])

时间复杂度：O(N)