题解 | 最少的完全平方数
最少的完全平方数
https://www.nowcoder.com/practice/4b2f5d4c00f44a92845bdad633965c04
import java.util.*;
// 完全背包的第二种情况
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int V = in.nextInt();//Volume
// 求解问题二
int []dp2 = new int [V + 1];
Arrays.fill(dp2, Integer.MAX_VALUE-1);//减1防止溢出，虽然这道题比较特殊，不会溢出
dp2[0] = 0;
for (int i = 1; i*i <= V; ++i) {//限制物品数
for (int j = i*i; j <= V; ++j) {//重量，顺序
dp2[j] = Math.min(dp2[j - i*i] + 1, dp2[j]);//价值默认为1,同时代表一件物品
}
}
System.out.println(dp2[V]);
}
}
SHEIN希音公司福利 370人发布