算法动态规划

哈希表优化DP

字数统计: 2k字   |   阅读时长: 9分
, , ,

摘要: 本文介绍了动态规划的一种优化方法：哈希表优化 DP。并拆解了 leetcode 上的 3 道题目。

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

当动态规划的转移方程是类似以下形式的时候：

计算 $dp[i]$ 时需要查询满足 $0 \leq j < i$, 且 $g(j) = h(i)$ 的 $j$ 中，$f(j) + dp[j]$ 的最大值，如果用遍历的方式，则转移的时间复杂度为 $O(N)$。

如果在推导状态的过程中维护一个哈希表，记为 mapping, 键是 $0 \leq j < i$ 对应的所有 $g(j)$，值 $mapping[x]$ 是 $0 \leq j < i$ 范围内 $g(j) = x$ 对应的 $f(j) + dp[j]$ 的最大值，则求 dp[i] 时，这步查询和可以用 mapping[h(i)] 直接得到，转移的时间复杂度变为 $O(1)$。

在 leetcode 中有 3 道题是用这个思路对动态规划进行优化的：

下面我们来解一下这三个题。

1218. 最长定差子序列

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

提示：

1
2
1 <= arr.length <= 1e5
-1e4 <= arr[i], difference <= 1e4

示例 1：
输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例 2：
输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

算法：动态规划

1
2
3
4
5
6
7
8
9
状态定义：
dp[i] := [0..i] 且以 i 结尾，最长等差子序列

初始化：dp[i] = 1

答案：max(dp[i])

状态转移：
dp[i] = max(1, 1 + max(dp[j]))  0 <= j < i 且 arr[j] + difference == arr[i]

代码 (C++)

注： O(N^2) 超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        if(arr.empty()) return 0;
        int n = arr.size();
        vector<int> dp(n, 1);
        // dp[i] := [0..i] 且以 i 结尾，最长等差子序列
        for(int i = 1; i < n; ++i)
        {
            int mx = 0;
            for(int j = 0; j < i; ++j)
            {
                if(arr[j] + difference == arr[i])
                    mx = max(mx, dp[j]);
            }
            dp[i] = max(dp[i], mx + 1);
        }
        int ans = 1;
        for(int i: dp)
            ans = max(ans, i);
        return ans;
    }
};

哈希表优化状态转移

在考虑 dp[i] 的转移时，需要以下查询:

  • 问: [0..i-1] 上有没有某个 j 使得 arr[j] 的值为 arr[i] - difference 的。如果有，最大的 dp[j] 是多少

将这一步查询用哈希表优化：

1
mapping[x] := arr[i] 为 x 时，dp[i] 的最大值

代码 (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
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        if(arr.empty()) return 0;
        int n = arr.size();
        vector<int> dp(n, 1);
        // dp[i] := [0..i] 且以 i 结尾，最长等差子序列
        unordered_map<int, int> mapping;
        // mapping[x] := arr[i] 为 x 时，dp[i] 的最大值
        mapping[arr[0]] = 1;
        for(int i = 1; i < n; ++i)
        {
            // 问: dp[0..i-1] 上有没有 arr[i] - difference
            // 如果有，最大的那一个 dp[j] 是多少
            if(mapping.count(arr[i] - difference) != 0)
                dp[i] = max(dp[i], 1 + mapping[arr[i] - difference]);
            mapping[arr[i]] = max(mapping[arr[i]], dp[i]);
        }
        int ans = 1;
        for(int i: dp)
            ans = max(ans, i);
        return ans;
    }
};

873. 最长的斐波那契子序列的长度

如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：

  • n >= 3
  • 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

提示：

1
2
3 <= arr.length <= 1000
1 <= arr[i] < arr[i + 1] <= 1e9

示例 1：
输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

示例 2：
输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

算法：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
dp[i][k]:= 考虑 arr[0..i] 且以 i 结尾，且上一个位置为 k 时的斐波那契子序列最大长度

初始化
dp[...][0] = 0
dp[0][...] = dp[1][...] = 0

答案
max(dp[i][k])

转移
dp[i][k] = max(3, dp[k][j] + 1)
其中 a[j] + a[k] = a[i]

代码 (C++)

$O(N^2 \log N)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int n = A.size();
        vector<vector<int> > dp(n, vector<int>(n, 0));
        int result = 0;
        for(int i = 2; i < n; ++i)
            for(int j = 1; j < i; ++j)
            {
                // [..k..j..i]
                // a[k] + a[j] = a[i]
                int target = A[i] - A[j];
                // 在 [0..j-1] 中找 target
                auto it = lower_bound(A.begin(), A.begin() + j - 1, target);
                if((*it) == target)
                {
                    int k = it - A.begin();
                    dp[i][j] = max(3, dp[j][k] + 1);
                    result = max(result, dp[i][j]);
                }
            }
        return result;
    }
};

优化

在转移的时候在 A[0..j-1] 中查找 target = A[i] - A[j] 用哈希表优化。

$O(N^2)$

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
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int n = A.size();
        // dp[i][j]:= [...,j, i] 的最大长度，从要么是0, 要么从3开始
        vector<vector<int> > dp(n, vector<int>(n, 0));
        unordered_map<int, int> mapping; // num -> idx
        for(int i = 0; i < n; ++i)
            mapping[A[i]] = i;
        int result = 0;
        for(int i = 2; i < n; ++i)
            for(int j = 1; j < i; ++j)
            {
                // [..k..j..i]
                // a[k] + a[j] = a[i]
                int target = A[i] - A[j];
                // 在 [0..j-1] 中找 target
                auto it = mapping.find(target);
                if(it != mapping.end() && (it -> second) < j)
                {
                    int k = it -> second;
                    dp[i][j] = max(3, dp[j][k] + 1);
                    result = max(result, dp[i][j]);
                }
            }
        return result;
    }
};

1027. 最长等差数列

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[ik] ，且 0 <= i1 < i2 < … < ik <= nums.length - 1。并且如果 seq[i+1] - seqi 的值都相同，那么序列 seq 是等差的。

提示：

1
2
2 <= nums.length <= 1000
0 <= nums[i] <= 500

示例 1：
输入：nums = [3,6,9,12]
输出：4
解释：
整个数组是公差为 3 的等差数列。

示例 2：
输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

示例 3：
输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

代码 (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
class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size();
        vector<unordered_map<int, int>> dp(n, unordered_map<int, int>());
        unordered_map<int, int> mapping; // d -> max_len
        for(int i = 1; i < n; ++i)
        {
            int d = A[i] - A[0];
            dp[i][d] = 2;
            mapping[d] = 2;
        }
        for(int i = 2; i < n; ++i)
        {
            for(int j = 1; j <= i - 1; ++j)
            {
                int d = A[i] - A[j];
                if(dp[j].find(d) != dp[j].end())
                {
                    dp[i][d] = dp[j][d] + 1;
                }
                else
                    dp[i][d] = 2;
                mapping[d] = max(mapping[d], dp[i][d]);
            }
        }
        int result = 0;
        for(auto iter: mapping)
            result = max(result, iter.second);
        return result;
    }
};

写在最后

动态规划有很多中优化方式，比较常见的如下图所示：

Share