谁能告诉我一个数能否表示为若干个完全平方数的和？
- 内容介绍
- 文章标签
- 相关推荐
本文共计450个文字，预计阅读时间需要2分钟。
动态规划，dp[i] 表示i有几个完全平方数的和构成，枚举比i小的完全平方数，状态转移方程为dp[i]=min(dp[i-k] + 1)，k就是完全平方数+1，题目大意+标签：动态规划 https://leetcode.cn/problemset/algorithm/
标签: 动态规划
leetcode.cn/problems/perfect-squares
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 <= n <= 104
动态规划，dp[i]表示i有几个完全平方数的加和构成，枚举比i小的完全平方数，状态转移方程为
dp[i] = min(dp[i-k] + 1) ，k就是完全平方数
class Solution {
public int numSquares(int n) {
// 找小于n的完全平方数
List<Integer> squares = new ArrayList<>();
for (int i = 1; i < n + 1; i++) {
int tmp = i * i;
if (tmp < n + 1) {
squares.add(tmp);
} else {
break;
}
}
int[] dp = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 1; i < n + 1; i++) {
for (int square : squares) {
if (i < square) {
break;
}
dp[i] = Math.min(dp[i], dp[i - square] + 1);
}
}
return dp[n];
}
}
四、总结小记
- 2022/6/21 坚持每天一道leetcode，养成一个习惯
本文共计450个文字，预计阅读时间需要2分钟。
动态规划，dp[i] 表示i有几个完全平方数的和构成，枚举比i小的完全平方数，状态转移方程为dp[i]=min(dp[i-k] + 1)，k就是完全平方数+1，题目大意+标签：动态规划 https://leetcode.cn/problemset/algorithm/
标签: 动态规划
leetcode.cn/problems/perfect-squares
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 <= n <= 104
动态规划，dp[i]表示i有几个完全平方数的加和构成，枚举比i小的完全平方数，状态转移方程为
dp[i] = min(dp[i-k] + 1) ，k就是完全平方数
class Solution {
public int numSquares(int n) {
// 找小于n的完全平方数
List<Integer> squares = new ArrayList<>();
for (int i = 1; i < n + 1; i++) {
int tmp = i * i;
if (tmp < n + 1) {
squares.add(tmp);
} else {
break;
}
}
int[] dp = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 1; i < n + 1; i++) {
for (int square : squares) {
if (i < square) {
break;
}
dp[i] = Math.min(dp[i], dp[i - square] + 1);
}
}
return dp[n];
}
}
四、总结小记
- 2022/6/21 坚持每天一道leetcode，养成一个习惯