算法动态规划

减治型区间DP，一个例子

字数统计: 1.4k字   |   阅读时长: 5分
,

摘要: 一个减治型区间 DP 的例子

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

对于区间动态规划来说，阶段是区间的长度，附加信息是区间的左右端点，其状态表示一般为 $dp[i][j]$ 表示区间 $[i,j]$ 上的某种指标，其中 $i, j$ 均为附加信息，阶段为 $j - i + 1$ 即区间长度。

推导状态的过程是按照长度从小到大的过程来的，在推导长度为 $l$ 的区间的状态时，长度为 $l - 1$ 的各个状态均已经推导完。

状态转移方程有两种比较常见的形式，一种转移方程是基于分隔点的，枚举 $[i, j]$ 中所有可能的分割点 $k$，考虑 $[i, k]$ 和 $[k + 1, j]$ 这两个子区间上的问题并将其结果整合得到候选答案：

这种情况在取分隔点 $k$ 后，子区间 $[i, k]$ 和 $[k+1, j]$ 上的子问题都需要求解，这与分治算法中分解后需要分别解决各个子问题，然后再合并出答案的过程很像，只是这里所有可能的分隔点 $k$ 都要走一遍这种求解两个子问题再合并答案的流程。因此称其为分治型区间 DP。

另一种是基于边界点的，考虑所有可能的边界点的情况，求解除边界点的剩余区间上的答案，然后与边界点对答案的贡献整合，得到候选答案：

在以上方程中，有三种边界点的情况，其中 $dp[i+1][j]$ 对应 $i$ 位置作为边界点的情况、$d[i][j-1]$ 对应 $j$ 位置作为边界点的情况、$dp[i+1][j-1]$ 对应 $i, j$ 作为边界点的情况。这与减治法的每次操作排除一部分元素的过程很像，因此称其为减治型区间 DP。这种转移方程常见于字符串的回文相关的问题中，根据端点字符是否相等做相应的状态转移。

根据具体的问题，边界点也会出现其它的情况，本文我看一个减治型区间 DP 的问题。

题目

给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：

  • 选择 nums 中最前面两个元素并且删除它们。
  • 选择 nums 中最后两个元素并且删除它们。
  • 选择 nums 中第一个和最后一个元素并且删除它们。

一次操作的 分数 是被删除元素的和。

在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。

请你返回按照上述要求 最多 可以进行的操作次数。

提示：

1
2
2 <= nums.length <= 2000
1 <= nums[i] <= 1000

示例 1：
输入：nums = [3,2,1,2,3,4]
输出：3
解释：我们执行以下操作：

  • 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。
  • 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。
  • 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。
    由于 nums 为空，我们无法继续进行任何操作。

示例 2：
输入：nums = [3,2,6,1,4]
输出：2
解释：我们执行以下操作：

  • 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
  • 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。
    至多进行 2 次操作。

题解

算法：动态规划

由于操作会从数组的两个端点进行，每执行一次操作，会将端点排除，答案加 1，然后继续剩余部分的问题，这就形成了最优子结构的雏形。而由于左端点右端点都有可能排除，剩余部分是一个子区间的形式，因此可以考虑减治型区间 DP。

定义 $dp[i][j]$ 表示去区间 $[i, j]$ 上，操作分数为 $s$ 的情况下的最多操作次数，这样定义的话，答案为 $dp[0][n-1]$，初始值为 $dp[i][i] = 0$、$dp[i][i-1]=0$。根据三种可能的操作，转移方程如下：

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from functools import lru_cache

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        @lru_cache(int(1e8))
        def solve(i, j, s):
            if i == j or j == i - 1:
                return 0
            ans = 0
            if nums[i] + nums[i + 1] == s:
                ans = max(ans, 1 + solve(i + 2, j, s))
            if nums[i] + nums[j] == s:
                ans = max(ans, 1 + solve(i + 1, j - 1, s))
            if nums[j - 1] + nums[j] == s:
                ans = max(ans, 1 + solve(i, j - 2, s))
            return ans

        n = len(nums)
        ans = 0
        ans = max(ans, solve(0, n - 1, nums[0] + nums[1]))
        ans = max(ans, solve(0, n - 1, nums[0] + nums[-1]))
        ans = max(ans, solve(0, n - 1, nums[-2] + nums[-1]))
        return ans
Share