【算法】动态规划专题⑪ —— 区间DP python

---

引入

区间动态规划（区间DP）适用于解决涉及区间最优化的经典问题，如石子合并、最长回文子序列等。

---

进入正题

石子合并 https://www.acwing.com/problem/content/284/

有 N 堆石子排成一排，其编号为 1,2,3,…,N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，
合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2，
又合并 1、2 堆，代价为 9，得到 9 2 ，
再合并得到 11，总代价为 4+9+11=24；

如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，
最后一次合并代价为 11，总代价为 4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。

输出格式
输出一个整数，表示最小代价。

数据范围
1≤N≤300

输入样例：

4
1 3 5 2

输出样例：

22

方法思路

1. 状态定义：定义 dp[i][j] 表示处理区间 [i, j] 的最优解。
2. 状态转移：通过枚举区间分割点 k，将问题分解为子区间 [i, k] 和 [k+1, j]，并合并结果。
3. 初始化：处理基础情况（如单个元素的区间）。
4. 计算顺序：按区间长度从小到大处理，确保子问题已解决。
   
   

题解code如下：

n = int(input())
a = list(map(int, input().split()))# 预处理前缀和数组，方便快速计算区间和
pre_sum = [0] * (n + 1)
for i in range(1, n + 1):pre_sum[i] = pre_sum[i - 1] + a[i - 1]dp = [[0] * (n + 1) for _ in range(n + 1)]  # dp[i][j]表示合并i到j堆的最小代价# 从2开始枚举区间长度
for length in range(2, n + 1):for i in range(n - length + 1):j = i + length - 1dp[i][j] = 10 ** 9# 枚举分割点kfor k in range(i, j):dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + pre_sum[j + 1] - pre_sum[i])
print(dp[0][n - 1])

代码解释

1. 输入处理：读取石子堆数和每堆的石子数量。
2. 前缀和数组：presum 数组用于快速计算区间 [i, j] 的石子总和。
3. DP数组初始化：dp[i][j] 初始化为0，当 i == j 时无需合并。
4. 区间遍历：外层循环枚举区间长度，内层循环确定区间起点 i 和终点 j。
5. 状态转移：遍历所有可能的分割点 k，计算合并代价并更新最小值。
6. 输出结果：dp[1][n] 表示合并所有石子的最小代价。

---

回归经典

最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

【算法】动态规划专题④ ——LCS（最长公共子序列）+ LPS（最长回文子序列） python

其他做法不多赘述，在此给出区间DP的做法：

1. 状态定义：dp[i][j] 表示字符串 s[i..j] 的最长回文子序列长度。
2. 初始化：单个字符的回文长度为1。
3. 状态转移：
   • 若 s[i] == s[j]，则结果为内部子串长度加2。
   • 否则，取舍去左端或右端后的最大值。
4. 计算顺序：从后向前遍历，确保 dp[i+1][j-1] 等子问题已计算。

code如下：

class Solution:def longestPalindromeSubseq(self, s: str) -> int:n = len(s)dp = [[0] * n for _ in range(n)]# 从后向前遍历，确保子问题先被计算for i in range(n - 1, -1, -1):dp[i][i] = 1  # 单个字符是长度为1的回文for j in range(i + 1, n):if s[i] == s[j]:dp[i][j] = dp[i + 1][j - 1] + 2else:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])return dp[0][n - 1]

---

总结

区间动态规划（Interval Dynamic Programming，简称区间DP）是一种特殊的动态规划类型，它主要处理那些可以分解为子问题的优化问题，而这些子问题往往与某个区间有关。

核心思想

• 划分问题：将原始问题划分为若干个子问题，每个子问题对应于一个区间。
• 状态表示：通常用二维数组dp[i][j]来表示从第i个元素到第j个元素之间的最优解。
• 状态转移方程：通过比较不同的分割点k，找到使得dp[i][j]取得最优值的分割方式。即dp[i][j] = min/max(dp[i][k] + dp[k+1][j] + cost) ，这里的cost是根据具体问题定义的合并成本或收益。
• 初始化：确定基础情况，如dp[i][i]，对于一些问题这可能是0或者是一个特定值。
• 计算顺序：由于区间长度逐渐增大，所以计算时需要先从小区间开始，逐步求解更长区间的值。

实现步骤

1. 确定状态：决定使用什么样的二维数组来存储子问题的答案。
2. 写出状态转移方程：这是最关键的部分，需要仔细分析如何利用已知的小规模问题的解来构建更大规模问题的解。
3. 边界条件处理：考虑最小规模的问题是如何解决的，并正确初始化。
4. 选择遍历顺序：通常按照区间长度从小到大进行遍历，确保在计算较大区间之前，所有较小的子区间已经被计算过。

掌握区间DP的关键在于理解其核心思想和实现逻辑，并能够灵活应用于各种具体的场景中。

---

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢