石子合并
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的，是找非法子序列的长度，不是子串）