在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 解决无权图最短路径的过程。

$$dp[v] = \min\limits_{uv \in E}dp[u] + 1$$

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

---

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 <= n <= 1e4

算法1：动态规划

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

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

$$dp[i] = \min\limits_{1 \leq j^{2} \leq i}(dp[i - j^{2}] + 1)$$

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

代码 (C++)

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++)

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++)

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;
    }
};

---