一、区间DP

1、状态表示

• f[i][j] 表示区间[i, j]的所有方案
• 初始化：区间长度为0的状态初始化

2、状态转移

思想：划分的左右两部分区间的计算不相互干扰
f[i][j] = min/max(f[i][j], f[i][k] + f[k+1][j] + cost)

3、基本模板 – 石子合并

import sys
input = lambda: sys.stdin.readline().strip()
n = int(input())
s = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
    s[i] += s[i - 1]
f = [[0x3f3f3f3f] * (n + 1) for _ in range(n + 1)] 
for i in range(1, n + 1):
    f[i][i] = 0

for l in range(2, n + 1):
    i = 1
    while i + l - 1 <= n:
        j = i + l - 1
        for k in range(i, j):
            f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1])
        i += 1

print(f[1][n])

二、 环形石子合并

1、解析

• 将序列倍增，环形转换为序列
• 对于序列区间DP，应用普通的模板

2、代码

import sys

n = int(input())
a = list(map(int, input().strip().split()))
a = [0] + a + a
for i in range(1, 2 * n + 1):
    a[i] += a[i - 1]

maxs, mins = [[0] * (2*n + 1) for _ in range(2*n + 1)], [[float('inf')] * (2*n + 1) for _ in range(2*n + 1)]
for i in range(1, 2 * n + 1): 
    mins[i][i] = 0
for lens in range(2, n + 1):
    l = 1
    while l + lens - 1 <= 2 * n:
        r = l + lens - 1
        for k in range(l, r):
            maxs[l][r] = max(maxs[l][r], maxs[l][k] + maxs[k + 1][r] + a[r] - a[l - 1])
            mins[l][r] = min(mins[l][r], mins[l][k] + mins[k + 1][r] + a[r] - a[l - 1])
        l += 1

print(min(mins[i][i + n - 1] for i in range(1, n + 1)))
print(max(maxs[i][i + n - 1] for i in range(1, n + 1)))

三、 能量项链

1、解析

• 将序列变为二元组，即(former, later)
• 边界分析：
  • 1)、初始化：求最大值（初始化0）
  • 2)、分界点k的取值：k只能等于l或r其中一个，根据乘法规定即可

2、代码

import sys

n = int(input())
a = list(map(int, input().split()))
w = []
for i in range(n):
    w.append((a[i], a[(i + 1) % n]))
w = [0] + w + w

f = [[0] * (2 * n + 1) for _ in range(2 * n + 1)]
for lens in range(2, n + 1):
    l = 1
    while l + lens - 1 <= 2 * n:
        r = l + lens - 1
        for k in range(l, r):
            f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + w[l][0] * w[k][1] * w[r][1])
        l += 1
print(max(f[i][i + n - 1] for i in range(1, n + 1)))

四、 加分二叉树

1、解析

• 给定二叉树的中序遍历，每次以根节点作为中间节点划分左右区间，两区间的计算必然不相互影响
• 从前往后遍历区间，只有答案变大才更新转移路径，必然字典序最小
• 初始化：根的状态和路径的初始化

2、代码

import sys
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
a = [0] + a
f = [[0] * (n + 1) for _ in range(n + 1)]
path = defaultdict(int)

for i in range(1, n + 1):  # 注意初始化
    f[i][i] = a[i]
    path[(i, i)] = i
for lens in range(2, n + 1):
    i = 1
    while i + lens - 1 <= n:
        j = i + lens - 1
        for k in range(i, j + 1):
            l_score = 1 if k == i else f[i][k - 1]
            r_score = 1 if k == j else f[k + 1][j]
            if f[i][j] < l_score * r_score + a[k]:
                f[i][j] = l_score * r_score + a[k]
                path[(i, j)] = k
        i += 1
def dfs(l, r):
    k = path[(l, r)]
    ans.append(k)

    if l <= k - 1: dfs(l, k - 1)
    if k + 1 <= r: dfs(k + 1, r)
ans = []
dfs(1, n)
print(f[1][n])
print(' '.join(map(str, ans)))

五、 凸多边形的划分

1、解析

• 多边形通过区间端点[i, j]以及中间节点k构成的三角形进行划分为左右两区间，显然不相互干扰
• 初始化：
  • 状态计算：由于每个三角形都要计算，中间节点的权重会被复用
  • 本题求最小值初始化为float(‘inf’)，对于区间长度为0和1由于无法构成三角形，初始化为0

2、代码

import sys

n = int(input())
w = list(map(int, input().strip().split()))
w = [0] + w
f = [[float('inf')] * (n + 1) for _ in range(n + 1)]
for i in range(n): # 注意初始化
    f[i][i + 1] = 0
    f[i][i] = 0

for lens in range(3, n + 1):
    i = 1
    while i + lens - 1 <= n:
        j = i + lens - 1
        for k in range(i + 1, j):
            f[i][j] = min(f[i][j], f[i][k] + f[k][j] + w[i] * w[k] * w[j])
        i += 1

print(f[1][n])