01_Introduction to DP 动态规划简介

动态规划简介

核心思想

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

---

示例 - 青蛙 1 (Frog 1)

题目描述

https://atcoder.jp/contests/dp/tasks/dp_a

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

---

解法

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

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

初始条件： - dp = [INF] * n：初始化为无穷大，表示尚未找到到达各石头的最小成本 - dp[0] = 0：起点成本为 0，青蛙已经在石头 1 上

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

INF = 10**18
n = int(input())
h = list(map(int, input().split()))

dp = [INF] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]))
    if i >= 2:
        dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))
    
print(dp[n - 1])

时间复杂度：O(N) 空间复杂度：O(N)