2026-08-23 05:59:29
MySQL 需要读写自身的数据库文件，但大多数应用数据库并不需要通过 SQL 语句与操作系统交换任意文件。如果一台数据库服务器主要用于 WordPress 或其他 Web 应用，那么启用这些并未使用的文件传输功能，只会增加不必要的攻击面。 下面两个 MySQL 配置可以提供一层非常实用的安全保护：
[mysqld]
local_infile=0
secure_file_priv=NULLlocal_infile=0 禁止从数据库客户端所在的机器加载文件，而 secure_file_priv=NULL 则禁止通过相关 SQL 操作直接读写 MySQL 服务器上的文件系统。两者的安全目标有所重叠，但不能互相替代。
LOCAL 指的是 MySQL 客户端所在的机器，而不是数据库服务器本身。
对比下面两条 SQL 语句：
LOAD DATA INFILE '/path/data.csv' INTO TABLE records;
LOAD DATA LOCAL INFILE '/path/data.csv' INTO TABLE records;LOCAL 时，MySQL 服务器进程会打开数据库服务器上的文件；带有 LOCAL 时，则由客户端程序打开本地文件，再把文件内容传送给 MySQL 服务器。
这一区别也解释了为什么两个配置都需要启用：
| 配置 | 保护的文件位置 | 主要影响的操作 |
|---|---|---|
local_infile=0 |
客户端主机，可能是应用服务器或 Web 服务器 | LOAD DATA LOCAL INFILE |
secure_file_priv=NULL |
MySQL 数据库服务器 |
LOAD DATA INFILE、SELECT ... INTO OUTFILE、SELECT ... INTO DUMPFILE 和 LOAD_FILE()
|
LOAD DATA LOCAL INFILE？LOAD DATA LOCAL INFILE 确实非常方便。不过，这项功能也跨越了一条重要的安全边界：MySQL 服务器会要求已连接的客户端读取本地文件，并把文件内容传送到服务器。
MySQL 官方文档指出了两个主要风险。首先，恶意或经过修改的数据库服务器可能要求客户端发送另一个文件，而不是客户端原本准备导入的文件。其次，在 Web 环境中，MySQL 的“客户端”通常实际上是 Web 服务器进程，因此可能受到威胁的是该进程有权读取的所有文件，而不只是管理员电脑上的文件。
还有一个原因需要谨慎对待 LOCAL：执行 LOAD DATA LOCAL 并不要求数据库账户拥有 MySQL 的全局 FILE 权限。它主要取决于服务器和客户端是否同时允许 LOCAL 功能。因此，在服务器端禁用它，可以建立一道明确而统一的安全边界：
local_infile=0LOAD DATA LOCAL INFILE。WordPress 数据库通常完全不需要这项功能，因此将其禁用是成本很低的最小权限实践。
secure_file_priv=NULL？secure_file_priv 变量控制可以直接与数据库服务器文件系统交互的 SQL 操作。在 MySQL 中，它的三种取值具有完全不同的安全含义：
| 取值 | 行为 |
|---|---|
| 空字符串 | 在数据库权限和操作系统权限允许的范围内，不限制文件导入和导出；MySQL 官方明确将其描述为不安全的配置 |
| 指定目录 | 只允许在指定目录中进行文件操作 |
NULL |
完全禁用相关的文件导入和导出操作 |
secure_file_priv=NULLFILE 权限，但配置错误可能发生，凭据可能被滥用，软件漏洞也可能让攻击者执行非预期的 SQL。即使管理员不慎授予了 FILE 权限，secure_file_priv=NULL 仍然可以提供一道服务器级别的最后防线。
secure_file_priv=NULL 能够禁止所有形式的文件加载，但它并不能保护客户端一侧的 LOCAL 路径。使用 LOCAL 时，读取源文件的是客户端，而不是 MySQL 服务器，因此服务器端的 FILE 权限和 secure_file_priv 限制并不控制这次读取操作。
反过来，local_infile=0 只会禁用带有 LOCAL 的加载方式。它本身无法阻止拥有足够权限的数据库账户使用 SELECT ... INTO OUTFILE 等服务器端文件操作。
因此，这两个配置分别关闭了两条互补的文件访问路径：
客户端文件系统 --X--> MySQL local_infile=0
MySQL --X--> 服务器文件系统 secure_file_priv=NULL[mysqld] 部分。该文件通常位于 /etc/mysql/mysql.conf.d/mysqld.cnf：
[mysqld]
local_infile=0
secure_file_priv=NULLsecure_file_priv 只能在 MySQL 启动时设置，因此修改配置后需要重启 MySQL：
sudo systemctl restart mysqlSHOW GLOBAL VARIABLES LIKE 'local_infile';
SHOW GLOBAL VARIABLES LIKE 'secure_file_priv';local_infile 的值为 OFF，secure_file_priv 的值为 NULL。
重启之后最好再检查一下 MySQL 错误日志。如果配置项放错了位置、存在重复设置、使用了无效值，或者多个配置文件的加载顺序与预期不同，最终生效的安全策略都可能与你写入的配置不同。
local_infile=0 会使依赖 LOAD DATA LOCAL INFILE 的工具或脚本无法工作，其中可能包括部分批量 CSV 导入工具和 MySQL Shell 导入流程。secure_file_priv=NULL 会阻止服务器端文件导入和导出，也会影响 mysqldump --tab 之类依赖数据库服务器创建文件的工作方式。
下面这种常规备份方式不会受到影响，因为数据库记录通过正常的客户端协议传输，再由 Shell 把输出内容写入文件：
mysqldump --single-transaction database_name > backup.sqlsecure_file_priv 限制到一个专用目录，要比将它设置为空字符串安全得多：
secure_file_priv=/var/lib/mysql-files/SELECT 查询读取数据库记录，也无法保护已经泄露的凭据，更无法限制已经获得操作系统访问权限的进程。它们同样无法弥补应用数据库账户权限过大的问题。
一套合理的数据库安全基线还应该包括：
FILE 权限；local_infile=0 和 secure_file_priv=NULL，可以在基本不影响正常应用查询和常规逻辑备份的情况下关闭这两条文件访问路径。这并不会让数据库变得绝对安全，但它能够缩小攻击面，并在其他安全措施失效时提供一道更坚固的最后防线——这正是纵深防御的价值所在。
兼容性说明：不同数据库产品和版本接受的配置值及默认行为可能不同。本文所介绍的 secure_file_priv=NULL 行为针对 MySQL。将相同配置应用到 MariaDB 或其他兼容 MySQL 的数据库之前，应先查阅对应产品的文档，并检查配置实际生效后的变量值。
英文：Hardening MySQL File Access with local_infile=0 and secure_file_priv=NULL
[show_posts keyword="MySQL"]
2026-08-22 02:24:07
一次清理Surface Laptop Studio 2硬盘时，我误用Shift+Delete永久删除了C盘下的tests目录，其中还包含未注意到的瑞士旅行照片。本文记录如何使用微软官方文件恢复工具WinFR，通过Regular和Extensive模式尝试恢复数据，并介绍SSD TRIM、恢复目标盘选择、机械硬盘恢复、回收站设置及RAID与真正备份之间的区别。我的 Microsoft Surface Laptop Studio 2 是两三年前买的，内置一块 2TB SSD，而且整个硬盘几乎都分给了 C 盘。 前不久，我发现 C 盘的剩余空间已经不到 200GB，于是便想清理一下不再需要的大文件。C 盘根目录下有一个名为
tests 的文件夹，我依稀记得这是去年编译 STEEM 区块链程序、下载区块数据时建立的测试目录。因为当时认定里面都是可以重新下载的数据，我连内容都没有仔细检查，就直接删除了。
更糟糕的是，删除时我还顺手按住了 Shift 键。
在 Windows 中，Shift+Delete 会绕过回收站，直接执行永久删除。删除开始后，我突然看到文件列表中出现了去年去瑞士时用单反拍摄的照片。等我反应过来并点击取消，已经太晚了：C:\tests 下面只剩下一些空目录，文件基本都被删掉了。
C:\tests 里面是不是还有其他没有备份的文件？
因此，我决定趁这个机会实际测试一下 Windows 自带的文件恢复工具——Windows File Recovery，也就是 WinFR。
这里必须强调一个容易混淆的概念：
RAID 1 不等于备份。
RAID 1 的主要作用是磁盘冗余：其中一块硬盘损坏后，另一块仍然可以继续工作。但是，如果误删文件、文件被病毒加密或者数据发生逻辑损坏，这些操作同样会被同步到两块镜像盘。
这次真正救了我的，并不是 RAID 1 本身，而是我曾经把照片从 Surface 的 SSD 复制到了另一个独立存储设备。也就是说，真正起作用的是“另一份独立副本”。
winfr 源盘: 目标盘: /模式 /n 路径过滤条件C:\testswinfr C: D: /regular /n \tests\C: 是发生误删除的源盘；D: 是保存恢复结果的目标盘；/regular 表示使用普通恢复模式；/n \tests\ 表示尽量只恢复原来位于 C:\tests 下的内容。\tests\、\TESTS\ 等写法通常没有区别。程序显示过滤条件为 TESTS\* 也是正常现象。
恢复完成后，WinFR 会在目标盘自动创建一个带有日期和时间的目录，例如：
D:\Recovery_20260813_230934
WinFr的使用方法还是挺简单的[/caption]
还有一个现实问题：我事先没有安装 WinFR，所以从 Microsoft Store 安装工具本身也会向 C 盘写入少量数据。对于普通恢复场景，这种风险或许可以接受；但如果丢失的是唯一一份、价值极高的数据，最稳妥的做法不是继续在原电脑上安装软件，而是立即停止使用甚至关机，考虑制作磁盘镜像或者交给专业数据恢复人员处理。
/regular 和 /extensive 有什么区别？/regular 模式/regular 适合以下情况：
winfr C: D: /regular /n \tests\/regular 很快找到了原来的目录结构和大量文件记录，扫描过程中显示的候选文件总数超过了18,000个。
/extensive 模式/regular 没有找到需要的文件，还可以继续尝试：
winfr C: D: /extensive /n \tests\/extensive 会执行更加彻底的扫描，适合以下情况：
/regular 没有找到目标文件。00%，并不一定代表程序已经死机。可以在任务管理器中观察源盘是否仍然存在持续读取活动。
微软的建议也是：最近从NTFS删除的数据先尝试 /regular，找不到后再使用 /extensive。
/regular 和 /extensive。两个模式都恢复出了大量文件，而且不少原始文件名和文件夹结构看起来都很完整。
但是，恢复出来的很多照片却无法打开，Windows提示文件已经损坏。
这其实并不矛盾。
NTFS中文件的元数据和文件实际内容并不是一回事。文件名、路径、大小和时间等信息通常记录在主文件表MFT中，而照片的实际内容则存储在其他数据块中。
删除文件之后，可能出现以下情况：
WinFr数据恢复过程的日志[/caption]
tests 的文件？tests，竟然还有：
Documents
Misc
Pictures
tests/regular。如果删除时间较长、磁盘经过格式化，或者文件系统不是NTFS，则可以尝试 /extensive。
因为机械硬盘通常没有SSD的TRIM行为，所以在数据没有被覆盖的前提下，误删文件的恢复成功率往往比SSD更高。
但是，这仍然不是保证：只要旧扇区已经被新数据覆盖，恢复工具同样无能为力。
设置 → 系统 → 存储 → Storage Sense删除回收站中存在时间超过……的文件Shift+Delete；
WinFR数据恢复后的日志/开始使用WinFr后建议不要再进行软件操作了/尽可能减少硬盘恢复过程中的操作[/caption]
[caption id="attachment_72754" align="alignnone" width="993"]
WinFr数据恢复过程的日志[/caption]
[caption id="attachment_72753" align="alignnone" width="331"]
每次恢复都会新建一个文件夹/时间戳/这样就不会覆盖掉现有的恢复的数据[/caption]
[caption id="attachment_72752" align="alignnone" width="762"]
WinFR恢复到另一个独立机械硬盘[/caption]
[caption id="attachment_72751" align="alignnone" width="937"]
WinFR数据恢复后的日志[/caption]
用了两三年笔记 C盘的寿命还有68%（固态硬盘）[/caption]
[show_posts keyword="硬盘"]
英文：Accidentally Deleting Over 18,000 Files with Shift+Delete: Recovering Data from a Surface SSD Using WinFR
2026-08-22 00:25:55
今年七夕临时走了两公里去剑桥 Grand Arcade，为老婆挑了一条价值309英镑的9ct黄金项链。虽然她收到礼物后想换成更喜欢、可能也更贵的款式，但我并不介意：七夕当天收礼物开心一次，周末挑新款还能再开心一次。老夫老妻也需要仪式感——礼物可以换，心意不能省。
中午就当消消食去购物商场给老婆挑七夕礼物[/caption]
从公司走了二十多分钟到达 Grand Arcade 后，我先去了 Pandora/潘多拉，还顺手注册了会员，可以享受九折优惠。随后又逛了两家珠宝店，最后在 H.Samuel 看中了一条9ct黄金项链。当年和媳妇谈恋爱的时候就到这家店买了情侣戒指。
以前我对英国金饰里的9ct、18ct并没有太多概念，于是现场又问了一下 ChatGPT，临时补习了一些金首饰知识。9ct代表黄金含量为37.5%，其余部分是其他金属合金。它的黄金纯度虽然没有18ct或中国常见的足金那么高，但硬度更高，也更适合做款式精细、需要经常佩戴的首饰，在英国珠宝店里很常见。
我最后选的是一条18英寸的9ct黄金长吊坠项链，价格309英镑。买之前还是小小地纠结了一会儿：一方面觉得一条看起来挺轻的项链卖三百多英镑并不便宜；另一方面又觉得，既然是过节送老婆，也没有必要每次都盯着性价比计算半天。于是刷卡、装盒，然后拎着礼物回家。
[caption id="attachment_72743" align="alignnone" width="2048"]
H.Samuel 9ct Yellow Gold Drop Lariat Pendant Necklace
上个月去泽西岛旅游 在一个海边的海鲜餐厅/媳妇[/caption]
和媳妇一起去喝咖啡休息[/caption]
H.Samuel 9ct Yellow Gold Cubic Zirconia Channel Set Cross
商品编号：4321227
当前价格：£229
材质：9ct黄金
镶嵌：透明立方氧化锆（Cubic Zirconia，简称CZ，不是钻石）
镶法：槽镶/轨道镶（Channel Set）
项链长度：16英寸
十字架宽度：12毫米
[caption id="attachment_72768" align="alignnone" width="1152"]
媳妇换了这个项链[/caption]
[show_file file="/var/www/wp-post-common/justyy.com/wife.php"]
[show_posts keyword="情人节"]
2026-08-20 23:38:31
去年虽然每天记录体重，却几乎没有变化。今年在收到NHS寄来的蓝牙体重秤后，我开始尝试16+8间歇性断食，并坚持每天做俯卧撑、纵跳和深蹲。几个月减重约3公斤后，ALT从最高的78降至38，重新回到正常范围。体重变化虽然不算巨大，身体却已经给出了积极反馈。
每天睡前称，其实不太准确，应该是早上起来拉完粑粑再称。不过我一般是睡前称，这样不容易忘记，和早上称的体重一般差1kg左右（一个晚上代谢1kg左右）[/caption]
其中最直观的是ALT，也就是丙氨酸氨基转移酶。它主要存在于肝细胞中，升高往往意味着肝脏正在承受某种压力。
我的ALT变化如下：
ALT（Alanine Transaminase，丙氨酸氨基转移酶/谷丙转氨酶）指标这次终于正常了。NHS抽血早上9:20左右，晚上18:05收到邮件说结果已经可以登陆mychart查询，这效率还可以。[/caption]
这次的AST是33，也在正常范围内；FIB-4为0.89，提示晚期肝纤维化风险较低；血小板等其他相关指标也正常。
这次抽血还检查了AST（Aspartate Transaminase），中文通常称为天门冬氨酸氨基转移酶或谷草转氨酶。AST与ALT类似，都是判断细胞是否受到损伤的重要指标，但ALT主要来自肝脏，而AST还广泛存在于肌肉和心脏等组织中，因此AST升高不一定完全由肝脏问题引起，剧烈运动或肌肉损伤也可能影响结果。我的AST是33 U/L，处于13—40 U/L的正常范围；结合已经恢复正常的ALT以及0.89的FIB-4评分，目前的肝脏相关检查结果总体令人放心。
当然，一次抽血结果恢复正常，并不能证明脂肪肝已经彻底消失，也不能把所有改善都简单归功于减掉的3公斤。但至少从目前的趋势来看，我所做的这些改变正在朝正确的方向发展。
Dear XXX, I heard back from the liver specialist - they are suggesting one further blood test to look at how the liver is functioning (a Fib4 test) and if that is OK we need take no further action at this stage. I'll add a link for you to book in for it. 我收到了肝病专科医生的回复——他们建议再做一次血液检查（Fib4 检查）以评估肝脏功能；如果检查结果正常，现阶段就无需采取进一步措施了。我会附上一个链接，方便你预约这项检查。肝脏专科后来回复说，还需要通过抽血做一次FIB-4评估；如果结果理想，现阶段就不需要采取进一步行动。严格来说，FIB-4并不是直接测量肝脏工作能力的单项检查，而是根据年龄、AST、ALT和血小板数量计算出来的肝纤维化风险指数，主要用来评估是否可能存在较严重的肝脏瘢痕。对于65岁以下成年人，FIB-4低于1.3通常属于低风险；我的结果是0.89，因此晚期肝纤维化的风险较低，也符合专科医生所说的“暂时无须进一步处理”。不过，低风险并不等于脂肪肝已经完全消失，今后仍需要继续控制体重、血糖和血脂，并按照医生建议定期复查。 下个月，Nuffield Health也会安排公司年度体检后的复查。Nuffield还提供一对一的健康指导，可以根据体重、饮食、运动和各项检查结果提出建议。 不过，无论是NHS、Nuffield、蓝牙体重秤，还是Second Nature App，它们能做的都只是提醒、记录和提供建议。最后真正需要执行的人，仍然是自己。
准确地说，FIB-4不是直接检测“肝脏工作能力”的单项指标，而是利用年龄、AST、ALT和血小板数量计算出来的肝纤维化风险评分。对于65岁以下成年人，低于1.3通常属于低风险；你的结果是 0.89，因此结果很好。[/caption]
[caption id="attachment_72725" align="alignnone" width="939"]
Aspartate transaminase（AST），中文叫天门冬氨酸氨基转移酶，也常称为谷草转氨酶。[/caption]
[caption id="attachment_72723" align="alignnone" width="1047"]
NHS抽血指标都正常（红白细胞/血小板等）[/caption]
[show_file file="/var/www/wp-post-common/justyy.com/nhs.php"]
[show_posts keyword="体检"]
2026-08-20 17:50:10
本文解析 LeetCode 279「完全平方数」的一种迭代加深递归解法。借助拉格朗日四平方和定理，算法只需依次判断一个数能否由一个、两个或三个完全平方数组成；如果都不能，答案必然是四。文章还分析了该递归实现的复杂度及优化方法，并与动态规划、广度优先搜索和纯数论解法进行比较。 视频：油管/Youtube | B站/小破站 | 微博视频 | 公众号视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书 | Facebook | Instagram
n，题目要求找出和为 n 的完全平方数的最少数量。
例如：
12 = 4 + 4 + 4，所以答案是 3。13 = 4 + 9，所以答案是 2。16 本身就是完全平方数，所以答案是 1。from math import isqrt
class Solution:
def numSquares(self, n: int) -> int:
sqrs = [i * i for i in range(1, isqrt(n) + 1)]
def f(cur, i):
if i == 1:
return cur in sqrs
for x in sqrs:
if f(cur - x, i - 1):
return True
return False
for i in range(1, 4):
if f(n, i):
return i
return 4
这段代码虽然很短，但其中包含了几个非常重要的思想。
n 的正完全平方数：
sqrs = [i * i for i in range(1, isqrt(n) + 1)]
例如，当 n = 13 时：
sqrs = [1, 4, 9]
我们需要考虑的最大平方数是：
isqrt(n) * isqrt(n)
Python 的 isqrt() 会直接返回准确的整数平方根，不需要使用浮点数运算。通常情况下，它比下面这种写法更合适：
int(n ** 0.5)
当 n 较小时，两种写法都可以正常工作。但是，isqrt() 的含义更加明确，并且可以避免大整数可能遇到的浮点数精度问题。
f(cur, i) 回答的是一个“是或否”的问题：
cur 能否恰好表示为 i 个正完全平方数之和？
例如：
f(13, 1) 判断 13 本身是不是一个完全平方数。f(13, 2) 判断 13 能否表示为两个完全平方数之和。f(12, 3) 判断 12 能否表示为三个完全平方数之和。if i == 1:
return cur in sqrs
如果 cur 是一个完全平方数，就说明找到了满足条件的表示方法。
否则，函数会选择一个平方数，将它从当前数值中减去，然后递归判断剩余部分能否由更少的平方数组成：
for x in sqrs:
if f(cur - x, i - 1):
return True
每一层递归都会重新从 sqrs 的开头遍历，因此同一个平方数可以被重复选择。这一点非常重要，因为有些答案需要重复使用相同的平方数，例如：
12 = 4 + 4 + 4
for i in range(1, 4):
if f(n, i):
return i
需要注意的是，range(1, 4) 只会生成：
1, 2, 3
算法并没有真正搜索由四个平方数组成的情况。如果前三次搜索全部失败，就直接返回 4。
这样做的依据是拉格朗日四平方和定理：
每一个正整数都可以表示为至多四个整数平方数之和。
因此，这道题的答案只可能是 1、2、3 或者 4。
算法按照从小到大的顺序检查这些答案，所以第一次成功时，得到的一定是最少数量。如果使用一个、两个或者三个完全平方数都无法组成 n，那么答案就只能是 4。
这个数学定理不仅仅是一个小优化。它正是递归搜索深度可以被限制在常数范围内的根本原因。
f(13, 1)
因为 13 不在 [1, 4, 9] 中，所以结果为 False。
接下来计算：
f(13, 2)
假设循环选择了 4，递归调用就会变成：
f(13 - 4, 1)
f(9, 1)
因为 9 是一个完全平方数，所以函数返回 True。也就是说：
13 = 4 + 9
最终答案是 2。
12 - 4 = 8
8 - 4 = 4
剩余的 4 是完全平方数。因此：
12 = 4 + 4 + 4
答案是 3。
sqrs 是一个列表：
cur in sqrs
令 m = floor(sqrt(n))，那么列表中一共有 m 个完全平方数。
在搜索三个平方数时，递归可能需要先选择两个平方数，然后才执行最后的成员查找。在最坏情况下，操作次数大约为：
m * m * m
因此，原始代码最坏情况下的时间复杂度是：
O(m³) = O(n^(3/2))
递归深度最多只有三层，所以递归栈使用的空间是常数级别。存储所有平方数的列表需要 O(sqrt(n)) 空间。
对于这道题相对较小的数据范围，这个简洁的实现仍然可以通过。不过，如果使用集合进行成员查找，就可以将平均查找时间降低到常数级别。
from math import isqrt
class Solution:
def numSquares(self, n: int) -> int:
squares = [i * i for i in range(1, isqrt(n) + 1)]
square_set = set(squares)
def can_sum(cur, count):
if count == 1:
return cur in square_set
# 剩余的 count - 1 个平方数都至少为 1
limit = cur - (count - 1)
for square in squares:
if square > limit:
break
if can_sum(cur - square, count - 1):
return True
return False
for count in range(1, 4):
if can_sum(n, count):
return count
return 4
递归仍然执行限深搜索，但最后一步判断一个数是否为完全平方数时，现在平均只需要 O(1) 时间。
对于三个平方数的情况，算法最多枚举两层平方数，第三个平方数通过集合直接判断。其最坏时间复杂度大约可以降低为：
O(m²) = O(n)
剪枝条件还可以阻止递归继续探索那些已经不可能容纳足够数量正完全平方数的分支。
dp[x] 表示组成 x 所需要的最少完全平方数数量。如果最后选择的平方数是 s，那么状态转移方程为：
dp[x] = min(dp[x], dp[x - s] + 1)
完整实现如下：
from math import isqrt
class Solution:
def numSquares(self, n: int) -> int:
squares = [i * i for i in range(1, isqrt(n) + 1)]
dp = [0] + [float("inf")] * n
for value in range(1, n + 1):
for square in squares:
if square > value:
break
dp[value] = min(
dp[value],
dp[value - square] + 1
)
return dp[n]
当 n = 12 时，部分状态如下：
dp[1] = 1，使用一个 1。dp[4] = 1，使用一个 4。dp[8] = 2，使用 4 + 4。dp[12] = 3，使用 4 + 4 + 4。n 个状态，每个状态最多需要检查 sqrt(n) 个完全平方数。
复杂度为：
O(n sqrt(n))
O(n)
x 出发，可以减去任何一个不大于 x 的完全平方数，从而到达下一个节点。
例如，从 13 出发，可以到达：
13 - 1 = 12
13 - 4 = 9
13 - 9 = 4
每一条边代表选择了一个完全平方数。因此，从 n 到 0 的最短距离，就是所需要的最少平方数数量。
from collections import deque
from math import isqrt
class Solution:
def numSquares(self, n: int) -> int:
squares = [i * i for i in range(1, isqrt(n) + 1)]
queue = deque([(n, 0)])
seen = {n}
while queue:
remaining, depth = queue.popleft()
for square in squares:
if square > remaining:
break
next_remaining = remaining - square
if next_remaining == 0:
return depth + 1
if next_remaining not in seen:
seen.add(next_remaining)
queue.append((next_remaining, depth + 1))
BFS 会先检查所有只使用一个平方数的表示方法，然后检查使用两个平方数的情况，再检查三个平方数的情况，以此类推。因此，它第一次到达 0 时，所经过的层数就是最少平方数数量。
最坏情况下的复杂度为：
O(n sqrt(n))
O(n)
4^a * (8b + 7)
因此，可以得到下面的实现：
from math import isqrt
class Solution:
def numSquares(self, n: int) -> int:
def is_square(value):
root = isqrt(value)
return root * root == value
if is_square(n):
return 1
for a in range(1, isqrt(n) + 1):
if is_square(n - a * a):
return 2
reduced = n
while reduced % 4 == 0:
reduced //= 4
if reduced % 8 == 7:
return 4
return 3
整体逻辑如下：
n 本身是完全平方数，返回 1。a，使得 n - a² 也是完全平方数，返回 2。4。3。O(sqrt(n))，额外空间复杂度为 O(1)。从渐进复杂度来看，这是最快的解法，但它依赖特定的数学定理，无法像动态规划那样直接推广到普通的硬币组合问题。
| 解法 | 时间复杂度 | 空间复杂度 | 主要优点 |
|---|---|---|---|
| 原始限深 DFS | O(n^(3/2)) |
O(sqrt(n)) |
代码非常简洁，直接利用四平方数上界 |
| 使用集合查找的 DFS | O(n) |
O(sqrt(n)) |
保留优雅的递归结构，同时提高查找效率 |
| 动态规划 | O(n sqrt(n)) |
O(n) |
通用性强，容易扩展到类似问题 |
| 广度优先搜索 | O(n sqrt(n)) |
O(n) |
具有直观的最短路径解释 |
| 数论 | O(sqrt(n)) |
O(1) |
理论复杂度最优 |
4 是缺乏逻辑依据的。有了这个定理，递归搜索的深度就永远不需要超过三层。
因此，与其将这个算法简单地称为暴力递归，不如称为“由数学定理引导的迭代加深限深搜索”。
原始实现已经非常简洁、易懂。它最主要的性能问题是 cur in sqrs 会对列表进行线性查找。增加一个集合后，就可以将完全平方数判断的平均时间复杂度降低到 O(1)，从而显著降低整个搜索的最坏时间复杂度。
对于这道特定题目，数论解法的效率最高。不过，从学习可复用算法模式的角度来看，动态规划和 BFS 更有价值。限深递归解法则处于两者之间：代码简洁、思路直观，同时很好地展示了数学知识如何大幅缩小算法的搜索空间。
[show_file file="/var/www/wp-post-common/justyy.com/teaching-kids-programming.php"]
[show_posts keyword="教娃"]
英文：Teaching Kids Programming - Minimum Number of Perfect Squares via Theorem-guided iterative deepening DFS
2026-08-18 23:43:29
多年后重听闽南语歌曲《欢喜就好》，才发现小时候觉得又土又俗的歌词，唱尽了普通人的欲望、纠结与不满足。得不到时嫌不够，得到了又怕失去；兜兜转转，人生最通透的道理或许就是：欢喜就好。 多年后重听《欢喜就好》，才发现唱的全是人生 小时候嫌土，长大后才听懂《欢喜就好》 《欢喜就好》：小时候听热闹，长大后听人生 人到中年，终于听懂了《欢喜就好》 《欢喜就好》：看似诙谐，唱的却是人生 从“嫌土”到“听懂”：多年后重听《欢喜就好》 一首《欢喜就好》，唱透普通人的纠结 得不到时嫌不够，得到了又怕失去 人生海海，欢喜就好 《欢喜就好》：兜兜转转，开心最重要 闽南语神曲《欢喜就好》：唱尽人生百态[caption id="attachment_72708" align="alignnone" width="2048"]
浙江卫视《天赐的声音》里再次听到《欢喜就好》：嫌饭菜煮得不好吃，嫌老婆不够漂亮 。[/caption]
[caption id="attachment_72707" align="alignnone" width="2048"]
浙江卫视《天赐的声音》里再次听到《欢喜就好》：整天嫌车不够拉风，嫌房车不够大。[/caption]
多年后，在浙江卫视《天赐的声音》里再次听到《欢喜就好》，一下子勾起了许多回忆。这是我最喜欢的一首闽南语歌。我喜欢的还有《爱拼才会赢》——这首应该是最家喻户晓的；刘德华的《世界第一等》也很经典；《风真透》很难唱，却有一种莫名的魔性；还有相对小众的《金包银》，也是越听越上头。
《欢喜就好》的原唱是陈雷，如今也已经六十多岁了。小时候听这首歌，只觉得又土又俗；到了这个年纪再听，才发现唱的哪里是玩笑，分明都是人生。
“吃得太好怕血压高”，一句话就把人的纠结唱明白了。整首歌看似也挺“矛盾”：嫌老婆不够漂亮，老婆太漂亮了又怕她跟别人跑，哈哈！嫌车不够气派，真开上好车又担心被偷；嫌房子不够大，住进大房子又嫌难打扫。
特别是这几句抱怨连在一起，听起来有些滑稽，却唱尽了人生百态：得不到时嫌不够，得到了又怕失去。人好像总能给自己找到不满足的理由，真是“自是人生长恨水长东”。
兜兜转转，才发现最通透的并不是什么大道理，而是最朴素的四个字：欢喜就好。😄
PS：我媳妇从小在莆田长大，后来才搬到福州，所以不太会说福州话。不过她觉得，闽南语和莆田话听起来有些相似。