区间DP问题一般从数组的左右两端不断缩短，求解关于某段下标区间的最优值，dp[i][j]一般定义为下标区间[i,j]的最优值

1.最长回文子序列问题

LeetCode516题 最长回文子序列

class Solution:def longestPalindromeSubseq(self, s: str) -> int:# dp[i][j]表示s[i: j + 1]的最长回文子序列长度dp = [[0] * len(s) for _ in range(len(s))]for i in range(len(s) - 1, -1, -1):for j in range(i, len(s)):if s[i] == s[j]:if j - i == 0:dp[i][j] = 1elif j - i == 1:dp[i][j] = 2else:dp[i][j] = dp[i + 1][j - 1] + 2else:# 此时肯定j>idp[i][j] = max(dp[i + 1][j], dp[i][j - 1])return dp[0][len(s) - 1]

LeetCode1771题 由子序列构造的最长回文串的长度

令s=word1+word2，在求s的最长回文子串的过程中，记录符合要求的答案

class Solution:def longestPalindrome(self, word1: str, word2: str) -> int:res = 0s = word1 + word2n = len(s)dp = [[0] * n for _ in range(n)]for i in range(n - 1, -1, -1):dp[i][i] = 1for j in range(i + 1, n):if s[i] == s[j]:dp[i][j] = dp[i + 1][j - 1] + 2if i < len(word1) <= j:res = max(res, dp[i][j])  # f[i][j] 一定包含 s[i] 和 s[j]else:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])return res

LeetCode647题 回文子串

动态规划解法

class Solution:def countSubstrings(self, s: str) -> int:res = 0# dp[i][j]表示s[i: j+1]是否为回文串dp = [[False] * len(s) for _ in range(len(s))]for i in range(len(s) - 1, -1, -1):for j in range(i, len(s)):if s[i] == s[j]:if i + 1 > j - 1:dp[i][j] = Trueelse:dp[i][j] = dp[i+1][j-1]if dp[i][j]:res += 1return res

双指针解法-空间复杂度低

class Solution:def countSubstrings(self, s: str) -> int:# 中心扩散函数def get_Center(s, l, r):count = 0while l >= 0 and r < len(s) and s[l] == s[r]:l -= 1r += 1count += 1return countres = 0for i in range(len(s)):res += get_Center(s, i, i) + get_Center(s, i, i+1)return res

LeetCode730题 统计不同回文子序列

647题的非连续子序列版本，且不能有重复

class Solution:def countPalindromicSubsequences(self, s: str) -> int:# dp[k][i][j]表示s[i:j+1]中以k（k是{'a','b','c','d'}中之一）为开头结尾的回文子序列个数mod = 10**9 + 7n = len(s)dp = [[[0] * n for _ in range(n)] for _ in range(4)]for i in range(n - 1, -1, -1):for j in range(i, n):for k, c in enumerate('abcd'):if s[i] == c and s[j] == c:if j - i == 0:dp[k][i][j] = 1elif j - i == 1:dp[k][i][j] = 2else:dp[k][i][j] = (2 + sum(d[i + 1][j - 1] for d in dp)) % modelif s[i] == c:dp[k][i][j] = dp[k][i][j - 1]elif s[j] == c:dp[k][i][j] = dp[k][i + 1][j]else:if j - i > 1:dp[k][i][j] = dp[k][i + 1][j - 1]return sum(d[0][n - 1] for d in dp) % mod

2.其他区间DP

LeetCode96题 不同的二叉搜索树

class Solution:def numTrees(self, n: int) -> int:# dp[i]表示i个不同的数组成的二叉搜索树的种类数# dp[i] = \sum dp[k - 1] * dp[i - k]  (1 <= k <= i)dp = [0] * (n + 1)dp[0] = 1for i in range(1, n + 1):for k in range(1, i + 1):dp[i] += dp[k - 1] * dp[i - k]return dp[n]

LeetCode375题 猜数字大小II

class Solution:def getMoneyAmount(self, n: int) -> int:# dp[i][j]表示当选的数字在区间[i, j]中时，确保获胜的最小现金数# dp[i][j] = min {max(dp[i][x - 1], dp[x + 1][j]) + x} 对x取mindp = [[float('inf')] * (n + 1) for _ in range(n + 1)]for i in range(n, 0, -1):for j in range(i, n + 1):# 当区间长度为1时，此时不需要支付if i == j:dp[i][j] = 0continuefor x in range(i, j + 1):if x == 1:dp[i][j] = min(dp[x + 1][j] + x, dp[i][j])elif x == n:dp[i][j] = min(dp[i][x - 1] + x, dp[i][j])else:dp[i][j] = min(max(dp[i][x - 1], dp[x + 1][j]) + x, dp[i][j])return dp[1][n]

LeetCode1130题 叶值的最小代价生成树

class Solution:def mctFromLeafValues(self, arr: List[int]) -> int:# dp[i][j]代表arr[i: j + 1]的非叶节点最小和# dp[i][j] = min{ dp[i][k] + dp[k + 1][j] + max(arr[i: k + 1]) * max(arr[k + 1: j + 1] }  i <= k <= j - 1# 求最值优化：# max_val[i][j]代表arr[i: j + 1]的最大值# max_val[i][j] = max(arr[i], max_val[i + 1][j])# dp[i][j] = min{ dp[i][k] + dp[k + 1][j] + max_val[i][k] * max_val[k + 1][j] }  i <= k <= j - 1n = len(arr)dp = [[float('inf')] * n for _ in range(n)]max_val = [[0] * n for _ in range(n)]for i in range(n - 1, -1, -1):max_val[i][i] = arr[i]dp[i][i] = 0for j in range(i + 1, n):max_val[i][j] = max(arr[i], max_val[i + 1][j])for k in range(i, j):dp[i][j] = min(dp[i][k] + dp[k + 1][j] + max_val[i][k] * max_val[k + 1][j], dp[i][j])return dp[0][n - 1]

LeetCode664题 奇怪的打印机

dp[i][j]代表的是字符串在区间[i:j+1]中需要最少的打印次数

• 打印一个字符串的次数为1，因此dp[i][i] = 1
• 当字符串长度大于等于2时，判断是否两边区间字符相等s[i] == s[j]
  • 如果相等，打印次数可以从子区间的打印次数转移而来dp[i][j] = dp[i][j-1];。例如aba的打印次数由ab的打印次数决定
  • 如果不相等，则枚举所有的可能组合，然后取其最优解

class Solution:def strangePrinter(self, s: str) -> int:# dp[i][j]表示打印s[i: j + 1]需要的最少打印次数# dp[i][j] = dp[i][j - 1] / min(dp[i][j], dp[i][k] + dp[k + 1][j]) i <= k <= jn = len(s)dp = [[n] * n for _ in range(n)]for i in range(n - 1, -1, -1):dp[i][i] = 1for j in range(i + 1, n):if s[i] == s[j]:dp[i][j] = dp[i][j - 1]else:for k in range(i, j + 1):if k == n - 1:dp[i][j] = min(dp[i][j], dp[i][k])else:dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])return dp[0][n - 1]

LeetCode312题 戳气球

class Solution:def maxCoins(self, nums: List[int]) -> int:# dp[i][j]表示戳破区间(i, j)内的所有气球能得到的最多硬币数，那么答案即为dp[0][n+1]# dp[i][j] = 对k取max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])，k表示是最后一个戳破的气球n = len(nums)nums = [1] + nums + [1]dp = [[0] * (n + 2) for _ in range(n + 2)]for i in range(n - 1, -1, -1):for j in range(i + 2, n + 2):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][n + 1]

LeetCode87题 扰乱字符串

class Solution:def isScramble(self, s1: str, s2: str) -> bool:# dp[i][j][l]表示s2[j: j + l]是否是s1[i: i + l]的扰乱字符串 1 <= l <= n - max(i, j)# dp[i][j][l] = (dp[i][j][k] and dp[i + k][j + k][l - k]) | (dp[i][j + l - k][k] and dp[i + k][j][l - k])#               1 <= k <= l - 1      n = len(s1)dp = [[[False] * (n + 1) for _ in range(n)] for _ in range(n)]for i in range(n):for j in range(n):dp[i][j][1] = (s1[i] == s2[j])for i in range(n - 1, -1, -1):for j in range(n - 1, -1, -1):for l in range(2, n - max(i, j) + 1):for k in range(1, l):# 分别对应不交换、交换情形dp[i][j][l] = dp[i][j][l] | \(dp[i][j][k] and dp[i + k][j + k][l - k]) | \(dp[i][j + l - k][k] and dp[i + k][j][l - k])return dp[0][0][n]