LeetCode 279 —— 完全平方数

1. 题目

2. 解题思路

此图利用动态规划进行求解，首先，我们求出小于 $n$ 的所有完全平方数，存放在数组 squareNums 中。

定义 dp[n] 为和为 $n$ 的完全平方数的最小数量，那么有状态转移方程：

$$dp[n]=min(dp[n-squareNums[i]]+1,dp[n]),对于任意squareNums[i]<n$$
$$dp[n]=1，对于squareNums[i]==n$$

3. 代码实现

class Solution {
public:int numSquares(int n) {vector<int> squareNums;for (int i = 1; i < n; ++i) {if (i * i > n) {break;}squareNums.push_back(i * i);}vector<int> dp(n+1, 10000);dp[1] = 1;for (int i = 2; i <= n; ++i) {for (int j = 0; j < squareNums.size(); ++j) {if (squareNums[j] > i) {break;} else if (squareNums[j] == i) {dp[i] = 1;} else {dp[i] = min(dp[i], dp[i - squareNums[j]] + 1);} }}return dp[n];}
};

时间复杂度为 $O(n\sqrt{n})$，第一层循环 $n$ 次，第二层循环 $\sqrt{n}$ 次，空间复杂度为 $O(n)$，其中 squareNums 占用空间为 $O(\sqrt{n})$，也可以省略，直接在第二个循环得到 $j\ast j$，dp 占用空间为 $O(n)$。