返回首页
完全平方数
LeetCode Hot 100
动态规划
难度:
中等
题目描述
计算数字 n 最少可以由几个完全平方数相加得到。
解题思路
使用动态规划，状态转移方程为 dp[i] = min(dp[i-j^2] + 1)，其中 j^2 ≤ i。时间复杂度为 O(n√n)。