01_Introduction to DP 动态规划简介
动态规划简介
使用备忘录优化朴素递归解法
Pro Tip: 通常先编写一个较慢的解法是个好主意。例如，如果获得全分的复杂度要求是 $O(N)$，而你想到一个简单的 $O(N^2)$ 解法，那么你首先应该编写这个解法并获得部分分数。之后，你可以逐步修改慢速解法的部分，直到达到所需的复杂度。慢速解法也可以作为压力测试的基准。
示例 - 青蛙 1 (Frog 1)
Focus Problem: 在继续之前，请尽力解决这个问题！
题目描述
题目要求我们计算青蛙从石头 $1$ 跳到石头 $N$ ($N \le 10^5$) 的最小总成本，已知青蛙只能跳一或两的距离。任意两个石头 $i$ 和 $j$ 之间的旅行成本由 $|h_i - h_j|$ 给出，其中 $h_i$ 表示石头 $i$ 的高度。
不使用动态规划
时间复杂度: $O(2^N)$
由于只有两种选择，我们可以使用递归来计算如果跳 1 块石头或 2 块石头会发生什么。有两种可能性，因此递归计算需要计算左右子树。因此，对于每增加一次跳跃，每个分支都会分裂成两个，这导致时间复杂度呈指数级。
然而，通过动态规划跟踪”最优状态”可以加快这一过程，以避免多次计算状态。例如，递归计算长度为 $1,2,1$ 和 $2,1,2$ 的跳跃会复用石头 $3$ 的状态。动态规划提供了缓存这些状态的机制。
使用动态规划
时间复杂度: $O(N)$
主要有两种动态规划方法：
- 推动态规划 (Push DP): 根据当前状态更新未来状态
- 拉动态规划 (Pull DP): 根据过去状态计算当前状态
推动态规划 (Push DP)
只有两种选择：跳一次或跳两次。定义 $dp[i]$ 为到达石头 $i$ 的最小成本。那么，我们的状态转移如下：
跳一个石头，成本为 $|heighti - height{i+1}|$:
跳两块石头，成本为 $|heighti - height{i+2}|$:
我们可以从基准情况 $dp[0] = 0$ 开始，因为青蛙已经在这个方格上，然后继续计算 $dp[1], dp[2], \dots, dp[N-1]$。
stone_num = int(input())
# height is 1-indexed so it can match up with dp
height = [0] + [int(s) for s in input().split()]
assert stone_num == len(height) - 1
"""
dp[N] is the minimum cost to get to the Nth stone
(we initially set all values to INF)
"""
dp = [float("inf") for _ in range(stone_num + 1)]
# dp[1] = 0 is our base case since we're already at the first stone
dp[1] = 0
for i in range(1, stone_num + 1):
if i + 1 <= stone_num:
dp[i + 1] = min(dp[i + 1], dp[i] + abs(height[i] - height[i + 1]))
if i + 2 <= stone_num:
dp[i + 2] = min(dp[i + 2], dp[i] + abs(height[i] - height[i + 2]))
print(dp[stone_num])拉动态规划 (Pull DP)
到达石头 $i$ 有两种方式：从石头 $i-1$ 和石头 $i-2$ 来。
从石头 $i-1$ 跳跃，成本为 $|heighti - height{i-1}|$:
从石头 $i-2$ 跳跃，成本为 $|heighti - height{i-2}|$:
我们可以从基准情况 $dp[0] = 0$ 开始，因为青蛙已经在这个方格上，然后继续计算 $dp[1], dp[2], \dots, dp[N-1]$。
N = int(input())
height = [int(s) for s in input().split()]
"""
dp[N] is the minimum cost to get to the Nth stone
(we initially set all values to INF)
"""
dp = [float("inf") for _ in range(N)]
# dp[0] = 0 is our base case since we're already at the first stone
dp[0] = 0
# for each state, process the states that lead to it
for i in range(1, N):
# jump one stone
if i - 1 >= 0:
dp[i] = min(dp[i], dp[i - 1] + abs(height[i] - height[i - 1]))
# jump two stones
if i - 2 >= 0:
dp[i] = min(dp[i], dp[i - 2] + abs(height[i] - height[i - 2]))
print(dp[N - 1])经典问题
接下来的几个模块将提供一些经典问题的例子：众所周知动态规划问题。然而，经典并不意味着常见。由于许多竞争者都了解这些问题，题目设计者很少直接使用它们。
注意 - DP 模块的顺序: 在开始其他 DP 模块之前，你不需要完成下面所有的问题。特别是，如果你的第一次接触 DP，我们建议你从背包模块的”简单”问题开始。