在DP状态转移的DAG上BFS:从动态规划的角度理解无权图最短路径

  |  

摘要: 在 DP 状态转移图上 BFS

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


在组合数学中,在很多与数列 $\{a_{n}\}$ 相关的问题:给定初始值 $a_{0}, a_{1},\cdots$ 以及一些规则,问 $\{a_{n}\}$ 的值。

如果我们把 $n = 0, 1, 2, \cdots$ 时数列的值 $dp[i]$ 视为一个个状态,基于给定规则写出状态转移方程,就可以用动态规划的方式解决。

本题的 DP 转移过程恰好就是在 DP 状态转移的 DAG 上求最短路径的过程,因此结合本题,我们就可以从动态规划的角度理解 BFS 解决无权图最短路径的过程。

此外,本题有数学背景,可以基于数论中的平方和相关的定理解决。


279. 完全平方数

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4

示例 2:
输入:n = 13
输出:2
解释:13 = 4 + 9

提示:

1
1 <= n <= 1e4

算法1:动态规划

定义 $dp[i]$ 表示和为 $i$ 的完全平方数的最少数量。初始时 $dp[0] = 0$,答案为 $dp[n]$。

在推导 $dp[i]$ 时,$[1, i]$ 范围内的所有平方数 $j^{2}$ 都构成一个可能的决策,从中选择使得 $dp[i]$ 最小的那一个即可。因此状态转移方程为:

共 $n$ 个状态,每次状态转移需要 $O(\sqrt{n})$,因此时间复杂度为 $O(n\sqrt{n})$

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int numSquares(int n) {
// n >= 1
vector<int> dp(n + 1, n);
dp[0] = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j * j <= i; ++j)
dp[i] = min(dp[i], dp[i - j * j] + 1);
return dp[n];
}
};

算法2:在状态转移 DAG 上 BFS

前面的推导过程是,当推导 $dp[i]$ 时,考虑 $dp[0],\cdots, dp[i-1]$ 有哪些状态可以转移到 $dp[i]$,完成 $dp[i]$ 的推导。

这里换一个方向,当推导完 $dp[i]$ 之后,考虑从 $dp[i]$ 可以转移到 $dp[i+1], \cdots, dp[n]$ 中哪些状态。更新 $dp[i]$ 对这些状态的贡献。

假设当前已经推导完 $dp[i]$,那么从 $1$ 开始枚举平方数 $j^{2}$,枚举范围是 $1 \leq j^{2} \leq n - i$,那么 $dp[i + j^{2}]$ 是从 $dp[i]$ 可以一步转移到的,并且 $dp[i + j^{2}] = dp[i] + 1$ 就是 $dp[i+j^{2}]$ 的最优决策。

$dp[i]$ 与 $dp[i + j^{2}]$ 之间视为连接了一条边权位 1 的有向边,那么 $dp[i]$ 就可以视为从 $i$ 到 $0$ 的最短路径,于是可以从 $dp[0]$ 出发走一轮 BFS 最短路径即可。

由 DP 状态组成的 DAG 中,点数 $V = n$,边数 $E = O(n\sqrt{n})$,由于 BFS 把每个顶点和每条边遍历一次,因此时间复杂度为 $O(V + E) = O(n\sqrt{n})$。

代码 (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
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, n);
queue<int> q;
dp[0] = 0;
q.push(0);
while(!q.empty())
{
int i = q.front();
if(i == n)
break;
q.pop();
for(int j = 1; i + j * j <= n; ++j)
{
if(dp[i + j * j] > dp[i] + 1)
{
dp[i + j * j] = dp[i] + 1;
q.puih(i + j * j);
}
}
}
return dp[n];
}
};

算法3:数论

费马二平方和定理(Fermat, 1640)

对正整数 $n$,将其分解为 $n = ml^{2}$,其中 $l^{2}$ 为平方部分,$m$ 为非平方部分。则 $n$ 为二平方和的充要条件是:$m$ 的所有素因子或者为 2,或者模 4 余 1。

勒让德三平方和定理(Legendre, 1798)

正整数 $n$ 不能表示为三平方和 $\Leftrightarrow$ $n$ 可以表示为 $4^{a}(8b + 7)$ 的形式,其中 $a, b$ 为任意非负整数。

拉格朗日四平方和定理(Lagrange, 1770)

每个正整数均为四平方和

由数论中关于平方和的若干定理,我们知道答案最大为 4,因此算法流程如下:

  • 如果 $n$ 是平方数,则答案为 1,二分求开方时间复杂度为 $O(\log n)$;
  • 若 $n$ 满足费马二平方和的条件,则答案为 2,试除法分解质因数时间复杂度 $O(\sqrt{n})$;
  • 若 $n$ 满足勒让德三平方和的条件(若满足条件,无法分解为三平方和),则答案为 4,$O(\log n)$;
  • 否则答案为 3。

代码 (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
45
46
47
48
49
50
51
class Solution {
public:
int numSquares(int n) {
int s = sqrt(n);
if(s * s == n)
return 1;

if(check_fermat(n))
return 2;

if(check_legendre(n))
return 4;

return 3;
}

bool check_fermat(int c) {
if(c == 0 || c == 1)
return true;
int p = 2;
for(int p = 2; p * p <= c; ++p)
{
int k = 0;
while(c % p == 0)
{
k++;
c /= p;
}
if((k & 1) && !_check(p))
return false;
}
if(c > 2 && !_check(c))
return false;
return true;
}

bool _check(int p)
{
// 费马二平方和定理
if(p == 2)
return true;
return p % 4 == 1;
}

bool check_legendre(int n)
{
while(n % 4 == 0)
n /= 4;
return (n % 8) == 7;
}
};

Share