关于算法:动态规划系列-区间DP

51次阅读

共计 1606 个字符,预计需要花费 5 分钟才能阅读完成。

石子合并

stones 形容 n 堆石子品质,每次能够合并相邻 2 堆石子,付出代价为 2 堆石子品质之和,问 n 堆石子合并为 1 堆石子的最小代价?

例如对于 stone = [1, 3, 5, 2]返回 22。

思考对于区间 [i, j],有断点 k,则合并[i, j] 的代价 cost(i, j)为 sum(stone[i:j+1]) + cost(i, k) + cost(k+1, j)。对于 sum(stone[i:j+1])咱们能够应用前缀和做优化。

DP 计划 1 :记忆化搜寻逆向 DP。

def solution(stones):
    n, prefix_sum = len(stones), [0]*(n+1)
    for i in range(n): prefix_sum[i] = stones[i] + prefix_sum[i-1]
    memory = [[0]*n for _ in range(n)]

    def search(i, j):
        if i == j: return 0
        if memory[i][j]: return memory[i][j]
        minimun = float('inf')
        for k in range(i, j):
            minimun = min(minimun, search(i, k) + search(k+1, j) + prefix_sum[j] - prefix_sum[i-1])
            memory[i][j] = minimun
        return minimun

    return search(0, n-1)

DP 计划 2 :枚举区间正向 DP。

def solution(stones):
    n = len(stones)
    prefix_sum = [0]*(n+1)
    for i in range(n): prefix_sum[i] = stones[i] + prefix_sum[i-1]
    status = [[0]*n for _ in range(n)]

    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            minimum = float('inf')
            for k in range(i, j):
                minimum = min(minimum, status[i][k] + status[k+1][j] + prefix_sum[j] - prefix_sum[i-1])
            status[i][j] = minimum

    return status[0][n-1]

最长无效括号

给定一个只蕴含 '('')' 的字符串,找出最长的蕴含无效括号的子串的长度。

例如对于 '(()(()’ 返回 2。

思考对于区间 [i, j],如果区间[i+1, j-1] 是非法的且 i,j 处匹配,那么 status[i, j] = status[i+1, j-1] + 2;接着须要枚举 [i, j] 内的区间,寻找两个相邻非法区间,取和最大值。例如对于 ”)()())” 中,只有枚举 [1, 4] 中的区间,能力计算出 status[1, 4] = 2 + 2 = 4。

def solution(s):
    if not s: return 0
    n, ans = len(s), 0
    status = [[0]*n for _ in range(n)]

    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if (length == 2 or status[i+1][j-1]) and (s[i], s[j]) == ('(', ')'):
                status[i][j] = status[i+1][j-1] + 2
            for k in range(i, j):
                if status[i][k] and status[k+1][j]:
                    status[i][j] = max(status[i][j], status[i][k] + status[k+1][j])
            ans = max(ans, status[i][j])

    return ans

留神:对该题目应用区间 DP 会超时,此处仅用此题举例,让读者能够验证本人代码的正确性。(最长非法括号子序列问题没找到,该问题对 '(()(()’ 是返回 4 的,是找非法子序列的长度,不是子串)

正文完
 0