哈希表优化DP

  |  

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

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


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

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

如果在状态转移的过程中维护一个哈希表,记为 mapping, 键是 0 ~ i 对应的 h(i),f(j) + dp[j] 的最大值,则求 dp[i] 是,这步查询和可以用 mapping[h(i)] 直接得到,转移的时间复杂度变为 O(1)

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

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


1218. 最长定差子序列

问题

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

分析

基础动态规划

1
2
3
4
5
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]
代码

注: 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] 的最大值

代码

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}
给定一个严格递增的正整数数组形成序列,找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在,返回 0 。

分析

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]

代码

O(N^2 logN)

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. 最长等差数列

问题

给定一个整数数组 A,返回 A 中最长等差子序列的长度。

代码

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