题单链接：https://atcoder.jp/contests/dp
A
入门题，直接放代码了
def solve():
n = int(input())
a = [0] + list(map(int, input().split()))
f = [0] * (n + 1)
f[1] = 0
f[2] = abs(a[2] - a[1])
for i in range(3, n + 1):
f[i] = min(f[i - 1] + abs(a[i] - a[i - 1]), f[i - 2] + abs(a[i] - a[i - 2]))
print(f[n])
B
A的加强版，多一个for
def solve():
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
f = [1 << 60] * (n + 1)
f[1] = 0
f[2] = abs(a[2] - a[1])
for i in range(3, n + 1):
for l in range(1, k + 1):
index = max(i - l, 1)
f[i] = min(f[i], f[index] + abs(a[i] - a[index]))
# for i in range(3, n + 1):
# f[i] = min(f[i - 1] + abs(a[i] - a[i - 1]), f[i - 2] + abs(a[i] - a[i - 2]))
print(f[n])
初始化不能乱设114514 😥，原来的f = [114514111145141] * (n + 1)会T
C
朴素转移
def solvec():
n = int(input())
f = []
for _ in range(n):
a, b, c = map(int, input().split())
f.append([a, b, c])
for i in range(1, n):
for j in range(3):
f[i][j] += max(f[i - 1][(j + 2) % 3], f[i - 1][(j + 1) % 3])
print(max(f[n - 1]))
D
01背包模板题 （妈的想起来去年这个时候自己也在听wls讲01背包
def solved():
n, m = map(int, input().split())
w = []
v = []
f = [0] * (m + 1)
for i in range(n):
x, y = map(int, input().split())
w.append(x)
v.append(y)
for i in range(n):
for j in range(m, w[i] - 1, -1):
f[j] = max(f[j], f[j - w[i]] + v[i])
print(f[m])
E
与上题相同，只不过$m$和$w_i$范围变到了$10^9$，就不能用相同的转移方程了 用$dp_i$表示价值到$i$所需的最小重量
def solvee():
n, m = map(int, input().split())
w = []
v = []
for _ in range(n):
x, y = map(int, input().split())
w.append(x)
v.append(y)
tot = sum(v)
# 这里的dp[i]表示到达价值为i所需的最小质量
dp = [1 << 31] * (10 ** 5 + 5)
dp[0] = 0
for i in range(n):
for j in range(tot, v[i] - 1, -1):
dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(tot, 0, -1):
if dp[i] <= m:
print(i)
return