跟着九章侯老师学习了动态规划专题之后根据学习所总结：
1 题目描述
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
2 示例
2.1 示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
2.2 示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
2.3 提示：
1 <= n <= 104
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
3 解题思路及方法
3.1 解题思路
3.1.1 确定状态
- 最后一步：关注最优策略中最后一个完全平方数j^2；
- 最优策略中n - j^2 也一定被划分成最少的完全平方数之和；
- 需要知道n - j^2 最少被分成几个完全平方数之和；
- 原来是求n最少被分成几个完全平方数之和
- 子问题：
- 状态：设f[i]表示i最少被分成几个平方数之和
3.1.2 转移方程
设f[i]表示i最少被分成几个平方数之和
3.1.3 初始条件和边界情况
-
设设f[i]表示i最少被分成几个平方数之和
-
文章来源：https://www.toymoban.com/news/detail-469979.html -
初始条件：0被分成0个完全平方数之和文章来源地址https://www.toymoban.com/news/detail-469979.html
- f[0] = 0
3.1.4 计算顺序
- 初始化f[0] = 0
- 计算f[1],f[2],…,f[n]
- 结果：f[n]
3.2 算法代码实现
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1);
int i, j;
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = INT_MAX;
for (int j = 1; j * j <= i; j++) {
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
};
到了这里，关于动态规划-完全平方数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
