🌕 279. 完全平方数

难度: 🌕

问题描述

---

解法

class Solution {
    public int numSquares(int n) {
        // 思路：
        // 自行填充含有的物品列表
        // 背包问题
        int len = (int)Math.pow(n, 0.5);
        int[] array = new int[len];
        for(int i = 0; i < len; i ++) {
            array[i] = (int)Math.pow(i + 1, 2);
        }
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n + 1);
        dp[0] = 0;
        for(int i = 0; i <= n; i ++) {
            for(int j = 0; j < len; j ++) {
                if(i - array[j] >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - array[j]] + 1);
                }
            }
        }
        if(dp[n] == n + 1) {
            return 0;
        }
        return dp[n];
    }
}

---

输出