区间DP，顾名思义是在区间上DP，它的主要思想就是先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。
有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。
示例 1：
输入：stones = [3,2,4,1], K = 2 输出：20 解释： 从 [3, 2, 4, 1] 开始。 合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。 合并 [4, 1]，成本为 5，剩下 [5, 5]。 合并 [5, 5]，成本为 10，剩下 [10]。 总成本 20，这是可能的最小值。示例 2：
输入：stones = [3,2,4,1], K = 3 输出：-1 解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.示例 3：
输入：stones = [3,5,1,2,6], K = 3 输出：25 解释： 从 [3, 5, 1, 2, 6] 开始。 合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。 合并 [3, 8, 6]，成本为 17，剩下 [17]。 总成本 25，这是可能的最小值。提示：
1 <= stones.length <= 30 2 <= K <= 30 1 <= stones[i] <= 100prefix用来O(1)存取sum(stones[i:j+1]) 状态转移方程： dp[i][j]代表【从i到j合并为最少堆的最小代价】 m：每次合并的区间长度，从K到N。m<K时已经初始化为0，所以不用遍历。 dp[i][i+m-1] = min(dp[i][k] + dp[k+1][i+m-1] for k in range(i, i+m-1, K-1)) + (prefix[i+m] - prefix[i] if (m-1)%(K-1) == 0 else 0) 分析：
min(dp[i][k] + dp[k+1][i+m-1] for k in range(i, i+m-1, K-1)) ： 之前已有的合并代价。为什么是k in range(i, i+m-1, K-1)？本质是需要左边的区间能够合并成一堆，或本身就只有一堆，右边的是减去这一堆后剩下的堆。若步长不为K-1，那么左右两堆合并时并不能确定合并的方式，比如 K=5，左边0~3，右边4~7，那还得计算是合并0~4？还是1~5？2~6？3~7？ prefix[i+m] - prefix[i] if (m-1)%(K-1) == 0 else 0： 当(m-1)%(K-1) == 0时，可以也必须进行合并成一堆的工作，此时用prefix计算合并代价。 这种方式下dp[0][n-1]本身的值看不出是否能合并成一堆，所以必须预先计算，所以开头有if (N - 1) % (K - 1): return -1
代码
class Solution: def mergeStones(self, stones: List[int], K: int) -> int: n = len(stones) if (n-1) % (K-1): return -1 pre = [0] * (n+1) # 前缀和 for i in range(1, n+1): pre[i] = pre[i-1] + stones[i-1] # 计算前缀和 dp = [[0] * n for _ in range(n)] for length in range(K, n+1): # 遍历区间长度 for i in range(n): # 遍历区间起点 j = i + length - 1 # 区间终点 if j > n-1: # 越界结束 break # 穷举分割点 dp[i][j] = min(dp[i][k] + dp[k+1][j] for k in range(i, j, K-1)) # 以下两行代码是错的，要注意，要用生成式语法 # for k in range(i, j, K-1): # dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) if (length-1)%(K-1) == 0: dp[i][j] += pre[j+1]-pre[i] return dp[0][n-1]有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明: 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100 示例:
输入: [3,1,5,8] 输出: 167 解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167思路： 以两个数作为左右端点，找出最优解中它们中间那个戳破的气球，中间这个气球把整个队列分为了2部分，要想让中间这个气球和2个端点靠在一起，就需要先把分开的2部分的气球戳破。 dp[i][j]表示i~j最大值，i，j不戳破。 比如k气球在i,j之间时(i,k,j)被戳破，那么要先戳破i,k、k,j之间的气球，所以dp[i][j]=dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j] dp[i][j]含义是不包含i,j的i-j之间的数组获得的最大乘积，所以在nums前后添加[1]
class Solution: def maxCoins(self, nums: List[int]) -> int: nums = [1] + nums[:] + [1] n = len(nums) dp = [[0] * n for _ in range(n)] # 逆向遍历，因为最后结果是dp[0][n-1], # 并且dp[i][j]需要通过dp[k][j]得到， # 而k>i，所以先要算出dp[k][j]，所以对i要逆向遍历 for i in range(n-1, -1, -1): for j in range(i + 2, n): # j>k。所以用正向遍历 for k in range(i + 1, j): # 不包含两端点 dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) return dp[0][-1]给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。 如： []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的
动态规划思路 状态定义：使用二维dp，dp[i][j]表示从s[i]到s[j]的最少添加括号个数 初始化：单独一个字符时，dp[i][j]＝１，因为一个字符必定需要添加一个括号，其他值先赋值为0 状态转移方程：循环遍历区间长度(区间长度m从1到n)，每次考虑[i，j]内的区间(i从0开始,j=i+m)，
如果s[i]和s[j]匹配，那么dp[i][j]=dp[i+1][j-1]，也即括号里面部分需要添加的最少括号数．分割情况：如果对区间[i,j]内的区间进行遍历分割，如果有更小的值，就采用更小的，也即 dp[i][j]=min(dp[i][j], dp[i][k] + dp[k+1][j])代码如下
def match(a, b): if a == '[' and b == ']': return True if a == '(' and b == ')': return True return False def kuohao(s): n = len(s) dp = [[0] * (n+1) for _ in range(n+1)] for i in range(n+1): dp[i][i] = 1 for m in range(1, n + 1): for i in range(n - m): j = i + m dp[i][j] = float('inf') if match(s[i], s[j]): dp[i][j] = dp[i + 1][j - 1] for k in range(i, j): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]) return dp[0][n - 1] s = '((]]()' print(kuohao(s))给出两个整数 n , m ,要求在 n 中加入m - 1 个乘号，将n分成m段，求出这m段的最大乘积
输入 第一行是一个整数T，表示有T组测试数据 接下来T行，每行有两个正整数 n，m ( 1<= n < 10^19, 0 < m <= n的位数)； 输出 输出每组测试样例结果为一个整数占一行 样例输入 2 111 2 1111 2 样例输出 11 121
题意： 给出一个数n,要求在n的数位间插入(m-1)个乘号，将n分成了m段，求这m段的最大乘积。
思路： 用dp[i][j]表示从第一位到第i位共插入j个乘号后乘积的最大值。根据区间DP的思想我们可以从插入较少乘号的结果算出插入较多乘号的结果。
当我们要放第j个乘号时枚举放的位置: 状态转移方程： dp[i][j]=max(dp[i][j],dp[k-1][j-1]*num[k][i]) nums[i][j]表示从s[i]到s[j]这段连续区间代表的数值
def int_split(s, m): n = len(s) nums = [[0] * n for _ in range(n)] # dp[i][j]表示在数组第一位到第i位共插入j个乘号后乘积的最大值 dp = [[0] * m for _ in range(n)] # 初始化nums for i in range(n): nums[i][i] = int(s[i]) # 第i位数字 for j in range(i+1, n): # 第i到第j位的数字 nums[i][j] = nums[i][j-1] * 10 + int(s[j]) for i in range(n): # 遍历数组结束位置，从0到第i个位置 dp[i][0] = nums[0][i] # 在数组中[0,i]中插入0个乘号，数组不变 for j in range(1, m): # 在数组中[0,i]中插入j个乘号，也即[1,m-1] if i < j-1: # 乘号数量大于数组长度 dp[i][j] = 0 else: dp[i][j] = -1 # 初始化为最小值 for k in range(1, i): # 遍历乘号的位置 dp[i][j] = max(dp[i][j],dp[k-1][j-1]*nums[k][i]) return dp[n-1][m-1] # 返回数组[0,n-1]中插入m-1个乘号的值 s = '1111' m = 2 print(int_split(s,m))给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。
假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。
示例 1：
输入：[1,2,3] 输出：6 解释：多边形已经三角化，唯一三角形的分数为 6。示例 2：
输入：[3,7,4,5] 输出：144 解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245， 或 3*4*5 + 3*4*7 = 144。最低分数为 144。示例 3：
输入：[1,3,1,4,1,5] 输出：13 解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。提示： 3 <= A.length <= 50 1 <= A[i] <= 100
对于点 0，1，…，n-1构成的多边形三角剖分，考虑点0和n-1，因为总有某个点 j 与点0和n-1构成三角形，
使得原多边形被分成一个三角形和至多两个凸多边形，求解原问题退化成求解两个规模更小的子问题，
即有若 f(0,n-1)表示原问题的解，则存在 j使 f(0,n-1) = f(0,j) + f(j,n-1) + A[0]*A[k]*A[n-1] 遍历 1~n-2的所有点找出这个j 使得得分最低即可
class Solution: def minScoreTriangulation(self, A: List[int]) -> int: n = len(A) dp = [[0] * n for _ in range(n)] for m in range(2, n): # 遍历长度 for i in range(n-m): # 遍历起点 j = i + m # 终点 dp[i][j] = float('inf') # 初始化 for k in range(i+1, j): # 遍历分割点 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i]*A[k]*A[j]) return dp[0][-1]