打卡记录

合并石头的最低成本（区间DP）

链接

与多边形的三角形问题相同，将大问题化小问题，再用中间节点不断地寻找最值。

class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        n = len(stones)
        if (n - 1) % (k - 1): return -1
        s = list(accumulate(stones, initial=0))
        f = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                f[i][j] = min(f[i][m] + f[m + 1][j] for m in range(i, j, k - 1))
                if not (j - i) % (k - 1): f[i][j] += s[j + 1] - s[i]
        return f[0][-1]