算法动态规划

方程组DP

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

摘要: 同一套阶段划分下的两套状态表示以及转移方程

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

本文我们看一个比较少见的动态规划问题。场景是两个串，按照两个串比较常见的思路，参考 LCS 问题，状态会定义成 $dp[i][j]$ 表示第一个串考虑到第 $i$ 个、第二个串考虑到第 $j$ 个的情况下的某个指标。

而本题是两个串各自有一个状态表示，而这两个状态表示用同一组阶段划分。

记这两个状态定义分别为 $f[i]$ 和 $g[j]$。

在当前阶段，第一个串对应的状态推导到了 $f[i]$，第二个串对应的状态推导到了 $g[j]$。要解决的状态计算问题是如何从前面阶段已经推导出的状态 $f[0],\cdots,f[i-1]$, $g[0],\cdots,g[j-1]$ 计算当前状态 $f[i]$，$g[j]$。

状态计算过程两个串对应的状态会互相依赖，也就是计算 $f[i]$ 会用到先前阶段算出两套状态 $f[i - 1]$ 和 $g[j-1]$、同样地，计算 $g[j]$ 也会用到先前阶段算出的 $f[i-1]$ 和 $g[j-1]$。

这样在推导阶段的过程中，$f[i]$ 和 $g[j]$ 也一起往前推倒。$f[i]$ 和 $g[j]$ 可以理解成同一个阶段划分下的一组状态转移方程。

题目

你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。

一条 合法路径 定义如下：

  • 选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
  • 从左到右遍历当前数组。
  • 如果你遇到了 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。

得分 定义为合法路径中不同数字的和。

请你返回 所有可能 合法路径 中的最大得分。由于答案可能很大，请你将它对 10^9 + 7 取余后返回。

提示：

1
2
3
1 <= nums1.length, nums2.length <= 1e5
1 <= nums1[i], nums2[i] <= 1e7
nums1 和 nums2 都是严格递增的数组。

示例 1：
输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
输出：30
解释：合法路径包括：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] （从 nums2 开始遍历）
最大得分为上图中的绿色路径 [2,4,6,8,10] 。

示例 2：
输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100]
输出：109
解释：最大得分由路径 [1,3,5,100] 得到。

示例 3：
输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
输出：40
解释：nums1 和 nums2 之间无相同数字。
最大得分由路径[6,7,8,9,10]得到。

题解

算法：动态规划

记状态定义 $f[i]$ 表示从 $a[0]$ 或 $b[0]$ 出发，走到 $a[i-1]$ 的路径的最大和。

记状态定义 $g[j]$ 表示从 $a[0]$ 或 $b[0]$ 出发，走到 $b[j-1]$ 的路径的最大和。

以上两组状态定义中，路径均可以在满足跳转条件时在两个串之间跳转。

我们要求的答案位 $\max(f[n1], g[n2])$。初始化 $f[0] = g[0] = 0$。

状态转移方程如下：

  • 若 $a[i - 1] < b[j - 1]$，则第一个方程向前推导
  • 若 $a[i - 1] > b[j - 1]$，则第二个方程向前推导
  • 若 $a[i - 1] = b[j - 1] = x$，则两个方程同时向前推导

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        vector<ll> f(n1 + 1);
        vector<ll> g(n2 + 1);
        int i = 1, j = 1;
        while(i <= n1 && j <= n2)
        {
            if(nums1[i - 1] < nums2[j - 1])
            {
                f[i] = f[i - 1] + nums1[i - 1];
                ++i;
            }
            else if(nums1[i - 1] > nums2[j - 1])
            {
                g[j] = g[j - 1] + nums2[j - 1];
                ++j;
            }
            else
            {
                f[i] = nums1[i - 1] + max(f[i - 1], g[j - 1]);
                g[j] = f[i];
                ++i;
                ++j;
            }
        }
        while(i <= n1)
        {
            f[i] = f[i - 1] + nums1[i - 1];
            ++i;
        }
        while(j <= n2)
        {
            g[j] = g[j - 1] + nums2[j - 1];
            ++j;
        }
        return max(f[n1], g[n2]) % MOD;
    }

private:
    using ll = long long;
    const int MOD = 1e9 + 7;
};
Share