题解 | #最少的完全平方数#

完全背包问题 思路：要求最少的完全平方数

输入n即为 体积

对于每一个完全平方数都是物品

物品 1 4 9

对应体积为 1 4 9

无价值，要求的是最少的完全数，所以不需要价值

要等于n 即为至少装满体积v1 也就是之前完全背包的第二问

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n + 1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        //输入5
        for(int i = 1; i * i <= n; i++) {//物品 1 2 
            for(int j = i * i; j <= n; j++) {//容量为5 
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        System.out.println(dp[n]);
    }
}