题解 | 最少的完全平方数

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]);
        
    }
}