#yyds干货盘点# 动态规划专题:最少的完全平方数

1.简述:

描述

给定一个正整数n,请找出最少个数的完全平方数,使得这些完全平方数的和等于n。

完全平方指用一个整数乘以自己例如1*1,2*2,3*3等,依此类推。若一个数能表示成某个整数的平方的形式,则称这个数为完全平方数。例如:1,4,9,和16都是完全平方数,但是2,3,5,8,11等等不是

数据范围:#yyds干货盘点# 动态规划专题:最少的完全平方数

输入描述:

仅一行,输入一个正整数 n 

输出描述:

按题目要求输出完全平方数之和为n的最少个数

示例1

输入:

5

输出:

2

说明:

1+4=5

示例2

输入:

8

输出:

2

说明:

4+4=8

示例3

输入:

9

输出:

1

说明:

3^2 = 9  32=9
import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
// init
// dp[i] = dp[i - j * j] + 1
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (j * j <= i) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
}
// 恰好体积为n
System.out.println(dp[n]);
}
}
发表评论

相关文章