分享最近遇到区间型 DP 的解题思路（为了赚到 188 大米看文章）

《经典区间型 动态规划 问题 》





遇到和之前的 ＤＰ问题比较不一样的题型，为了加深印象，决定来记录一下！


「经典的射气球ＤＰ问题」
题目的目标是要刺破一排气球，并在每次刺破气球时，根据周围气球的数值来计算得分，最终需要找出一种刺破的顺序，使得得分最高。



💥 先从暴力解开始

最直接的方法就是把所有可能的刺破顺序列出来，对每种顺序计算总分，然后取最高的分数。但这种方法的时间複杂度会非常高，最少也要 O(n!)，因为要考虑所有的排列组合。随着气球数量增加，这种方法会变得不可行。

💡 动态规划的思路：



1. 定义子问题：
我们用 solve(nums, i, j) 来表示「刺破从第 i 个气球到第 j 个气球之间所有气球的最高得分」，接下来的问题是如何把这个区间进一步拆解。


2. 选择第 k 个气球：
当我们选定 kth 气球作为要刺破的气球时，会得到分数 nums[k-1] * nums[k] * nums[k+1]，但如果我们尝试这么做，该问题就会被切分成更小的子问题 → solve(nums, i, k - 1), solve(nums, k + 1, j)，会发现刺破一个气球会改变相邻气球的状态（气球 k - 1 and k + 1 会变成是相邻的）


这意味着❗子问题彼此并不互相独立❗，计算会变得複杂，无法简单分离。


3. 不同的思维方式：
与其考虑先刺破哪颗气球，不如反过来思考——「假设第 k 个气球是整个区间 [i, j] 中最后被刺破的气球」 这样就可以把问题分成两个独立的子问题：刺破 [i, k-1] 区间的所有气球，和刺破 [k+1, j] 区间的所有气球，因为在这两个区间内，气球 k 已经是最后一个被刺破的，其他气球的影响就不会交叉。 


4. 计算得分：
对于每个从 i 到 j 的气球 k，如果 kth 是最后破掉的气球，表示 [i, k-1] 和 [k+1, j] 的气球也都已经被刺破了，那得分会是 nums[i-1] * nums[k] * nums[j+1]。
最后，我们只需要把所有可能的 k 气球得分算出来，并选择最高的得分来更新 solve(nums, i, j) 的结果。


5. 边界处理：
为了处理第一颗和最后一颗气球的情况，我们可以在原始气球阵列的两端加上 1，这样当气球被刺破时，边界的气球得分就可以统一用 1 当作乘数，避免特殊处理。 


6. 解题步骤总结：

• 定义 dp(i, j) 表示从 i 到 j 的最高得分。
• 从小的区间开始计算，逐步扩展到更大的区间。
• 对每个区间，考虑每个气球作为最后被刺破的情况，计算得分并更新 DP table。
• 最后，dp(1, n)（n 为气球数量）即为整个问题的最佳解。

👉🏻 这个解法的时间複杂度是 𝑂(n^3)，比 Brute Force 的 𝑂 (n!) 好很多，适合较大的输入范围。 

附上程式码

• 时间複杂度是 𝑂(n^3)
• 空间複杂度是 𝑂(n^2) 

（第一次发帖子，如果内容有任何需要改进的地方，欢迎指教！）

462669025_1587000181885261_1906535510591845809_n.jpg

区间DP & 数位DP 是我觉得唯二觉得用记忆化搜索比递推好些的DP，推荐一下！

OnjoujiToki 发表于 2024-10-17 19:01
区间DP & 数位DP 是我觉得唯二觉得用记忆化搜索比递推好些的DP，推荐一下！

当我每次将递推转换为记忆化搜索时，常常会遇到初始值和循环边界的问题，以及在更新时的条件没有写好的情况。不知道有没有什么技巧可以传授一下？

1.     def maxCoins(nums: List[int]) -> int:
   
2.         n = len(nums)
   
3.         nums = [1] + nums + [1]
   
4.         dp = [[0] * (n + 2) for _ in range(n + 2)]
   
5. 
   
6.         for length in range(1, n + 1):
   
7.             for i in range(1, n + 1):
   
8.                 j = i + length - 1
   
9.                 if j > n:
   
10.                     continue
    
11.                 for k in range(i, j + 1):
    
12.                     dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j + 1])
    
13. 
    
14.         return dp[1][n]

复制代码

haikyo 发表于 2024-10-17 08:18
当我每次将递推转换为记忆化搜索时，常常会遇到初始值和循环边界的问题，以及在更新时的条件没有写好的情 ...

emmm说不好，感觉一般人都是反着来，比如从记忆化搜索转化成递推。。
如果写记忆化搜索的话一般是从递归开始考虑，初始值的考虑方式和递推是一样的。边界的话，记忆化搜索甚至还能剪枝，这一点理论上是稍微比递推复杂一些的，感觉没有一个很通用的规律解答你的问题。

好帖，但是发错论坛了哥们

Valkyrie_GaN 发表于 2024-10-18 02:10
好帖，但是发错论坛了哥们

对不起，昨天确实找了很久，不知道发在哪里适合些，请问下次我这样的文章，该发哪边好了？

区间dp就是遍历区间所有元素的dp
所有的公式都基本是下面的模式。。

1. dp(i, j) = max(dp(i, k)+dp(k, j), dp(i, j))
   
2. =====
   
3. k是(i, j)区间的index

复制代码