【LeetCode】279. 完全平方数
目录
- 题目描述
- 输入输出示例及数据范围
- 思路
- C++ 实现
题目描述
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
输入输出示例及数据范围
思路
又是一道我之前已经做过许多遍但这一次仍然做不出来的题，遂在此整理一下这道题的思路。
这道题需要使用动态规划来解决，具体来说，假设我们有一个长度为n的数组f，f[n]代表的就是对于整数n，最少可以用多少个完全平方数的加和来表示它，
1
,
4
,
9
,
16
,
.
.
.
1, 4, 9, 16, ...
1,4,9,16,...这些数都是完全平方数。
看到这里自然可以想到，在状态转移的过程中，可能会牵涉到f[i - j * j]，初步的思路确实没问题，但是我卡在这里不知道下一步应该做什么了。
由于题目要求的是，最少可以用多少个完全平方数来表示目标整数，我们遂从1开始向n枚举，比如对于某个数i，既然我们想要知道最少可以用多少个完全平方数来表示它，那么我们从1开始枚举完全平方数，假定现在枚举到j，满足j * j <= i。显然，我们在f[i - j * j]的基础上加1，就是使用最少完全平方数表示i的答案，因为f[i - j * j]本身的含义就是表示i - j * j这个数所需要的完全平方数的最小数目。
我们在枚举j的过程中，是从1开始枚举的，约束条件为j * j <= i，只要在这个过程中找到最小的f[i - j * j]，即可更新f[i]。
C++ 实现
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, 0);
for(int i=1; i<=n; i++) {
int minn = INT_MAX;
for(int j=1; j*j<=i; j++) {
minn = min(minn, dp[i - j * j]);
}
dp[i] = minn + 1;
}
return dp[n];
}
};