哈希表优化DP

  |  

摘要: 本文介绍了动态规划的一种优化方法:哈希表优化 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