【算法】区间DP

基本内容

[!NOte]

通过分治的思想实现DP数组

• 入门例子 NOI1995] 石子合并 - 洛谷 | 计算机科学教育新生态

题目要求：给定一圈石头数组，每个石头对应一个权重值，当两个石头合并时组成一个小石头堆，成本为两个石头权重值相加，当两个石头堆合并时组成一个大石头堆， 成本为两个小石头堆的权重值相加。

• 例子简化

​ 先从简单的情况入手，不考虑围成圈的情况，假设石头堆是连续的数组，首尾不连接

​ 不难发现，最后一次合并所需要的成本一定是所有石头的权重值之和，最后剩下的两堆石头可能为：【4】和【5，9，4】或者【4，5】和【9，4】或者【4，5，9】和【4】，所有情况的最后一次合并的成本是一个常数项，假设合成最后一个大堆的两个小堆分别为smallA,smallB, 则合成的所需的成本为：
$$value=valu{e}_a+valu{e}_b+C$$
其中C为最后一次合并的成本，因此，只要求出$valu{e}_a$和$valu{e}_b$的最小值即可。

​ 通过以上思路，可以对smallA，smallB进一步进行划分为更小的堆，直到堆的石头个数为1，即为最小的堆。

• 代码变量解释

[!note]

目前求合成石头堆的最小成本，我们已经知道只有找到两个组成这个大堆的成本最小的堆即可，因此需要在一个二维数组中存取从 L到R石头合成的最小成本。

​ f[i][j]：二维数组，表示合成第i个石头到第j个石头所需的最小成本；

​ g[i][j]：二维数组，表示合成第i个石头到第j个石头所需的最大成本；

​ s：前缀和数组，方便计算石头堆最后一次合并的成本C

• 解题代码

N = int(input())
stones = list(map(int, input().split()))
f = [[0 for i in range(len(stones))] for i in range(len(stones))] 
g = [[0 for i in range(len(stones))] for i in range(len(stones))]
s = [0] * (len(stones) + 1)
# 计算前缀和
for i in range(1, len(stones) + 1):
    s[i] = stones[i - 1] + s[i - 1]
# 一个大堆是由两个中堆组成，一个中堆又有两个小堆组成...,因此需要遍历合成一个小堆的个数，最小的堆是2
for length in range(2, len(stones)+1):
    l = 0
    while l + length -1  < len(stones):
        r = l + length - 1
        f[l][r] = float("inf")
        g[l][r] = -float("inf")
        for k in range(l,r):
            f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r+1] - s[l])
            g[l][r] = max(g[l][r], g[l][k] + g[k+1][r] + s[r+1] - s[l])
        l += 1
print(f[0][len(stones)-1])
print(g[0][len(stones)-1])

• 围成圈的情况

💡 所有围成圈的算法题，都可以视为是普通队列的特殊情况，以石头合并的例子为例，一个石头数组的长度为N，可以将石头数组延长一份，并且以大小为N的窗口大小移动，即可得到最终的结果，在时间复杂度上需要$\times$2

• 最终代码

N = int(input())
stones = list(map(int, input().split()))
stones = stones + stones
f = [[0 for i in range(len(stones))] for i in range(len(stones))]
g = [[0 for i in range(len(stones))] for i in range(len(stones))]
s = [0] * (len(stones) + 1)
# 计算前缀和
for i in range(1, len(stones) + 1):
    s[i] = stones[i - 1] + s[i - 1]
for length in range(2, N+1):
    for l in range(2 * N - length + 1):
        r = l + length - 1
        f[l][r] = float("inf")
        g[l][r] = -float("inf")
        for k in range(l,r):
            f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r+1] - s[l])
            g[l][r] = max(g[l][r], g[l][k] + g[k+1][r] + s[r+1] - s[l])
minV = float("inf")
maxV = -float("inf")
for i in range(N):
    minV = min(minV, f[i][i+N-1])
    maxV = max(maxV, g[i][i+N-1])
print(minV)
print(maxV)

题目

1. 1547. 切棍子的最小成本

题目要求：

cuts = [0] + sorted(cuts) + [n]
length = len(cuts)

# 初始化 DP 数组
f = [[0] * length for _ in range(length)]

# 动态规划计算最小切割代价
for len_interval in range(2, length):  # 区间长度
    for l in range(length - len_interval):  # 左边界
        r = l + len_interval  # 右边界
        f[l][r] = float("inf")
        # 选择切割点 k，使得当前切割的代价最小
        for k in range(l + 1, r):
            f[l][r] = min(f[l][r], f[l][k] + f[k][r] + cuts[r] - cuts[l])

return f[0][length - 1]