1

class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        // dp[0] = true;有没有都没影响
        if (nums[0] <= target) {
            dp[nums[0]] = true;
        }
        for (int i = 1; i < len; i++) {
            for (int j = target; j >= 0 && nums[i] <= j; j--) {
                //逆序遍历是不能覆盖之前的值，因为只用一维数组，当前元素的值由上一行或上一行左边某个值得来
                dp[j] = dp[j] || dp[j - nums[i]];
            }
            if (dp[target]) {
                return true;
            }
        }
        return dp[target];
    }
}

2

class Solution {
    public int numSquares(int n) {
        //dp[i] 表示当前数字i最少由几个完全平方数构成
        //dp[i] = Math.Min(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*i<=n;i++){
            int x = i*i;
            for(int j = x;j<=n;j++){
                dp[j] = Math.min(dp[j],dp[j-x]+1);
            }
        }
        return dp[n];
    }
}

标签：动态规划
首先初始化长度为 n+1 的数组 dp，每个位置都为 0
如果 n 为 0，则结果为 0
对数组进行遍历，下标为 i，每次都将当前数字先更新为最大的结果，即 dp[i]=i，比如 i=4，最坏结果为 4=1+1+1+1 即为 4 个数字
动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i 表示当前数字，j*j 表示平方数
时间复杂度：O(n*sqrt(n))O(n∗sqrt(n))，sqrt 为平方根
class Solution {
    public int numSquares(int n) {
        //dp[i] 表示当前数字i最少由几个完全平方数构成
        //dp[i] = Math.Min(dp[i],dp[i-j*j]+1);
        int[] dp = new int[n+1];
        for(int i=1;i<=n;i++){
            dp[i] = i; //每次最坏的情况就是+1
            for(int j = 1;i-j*j>=0;j++){
                dp[i] = Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}