279. Perfect Squares

问题

原问题是说，给一个正整数n，找出最小数量的平方数并且这些平方数的和为n。或者说反过来，一个n，最少能分解成平方数的数量。

解析

这个题目我一开始想的时候，想n=1的时候，结果为1（只有一种情况）；那么从1开始如何得到2的结果？那就是1的结果加上 2-1的结果，同理3的结果就是2的结果加上3-2的结果；

但是到4情况变了，4本身他自己是一个平方数。那么组成他的数最少数量是1，也就是他自己。

想了一会，其实是之前的一道完美平方数的题目给了一点思路，忘了具体是哪道了，反正就是在初始化其实也可以把小于n的所有的平方数的结果都置为1。

到这这个题目就是就已经比较明显了，初始化解决了，当前的结果如何从前面的结果推导出也解决了（状态转移）。

代码1

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 1; i*i <= n; i++) {
            dp[i*i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.min(dp[i], dp[j] + dp[i-j]);
            }
        }
        return dp[n];
    }
}

代码2

这个是我提交代码后看到的别人的一种写法，比我的快很多。我就琢磨了一下他这个写法。

首先他不用初始化每一个平方数，在状态转移的过程中直接就可以得到。

他这比较巧妙的是，运用了dp0这个值，另外就是只看平方数相关的结果，因为我们可以推导出来，结果应该是出于某些大平方数（区别于全都是加一）相加，所以只看其相关的结果即可。

代码中dp[i - j * j] + 1,这个加一，其实就是i - j * j中j*j的结果即1。

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

Perfect Squares

Problem

The original problem is to find the smallest number of squares that sum to n given a positive integer n. Or conversely, the smallest number of squares an n can be decomposed into.

Analysis

When I first thought about this topic, I thought that n=1 results in 1 (there is only one case); so how do you get the result of 2 starting from 1? That is, the result of 1 plus the result of 2-1, and similarly the result of 3 is the result of 2 plus the result of 3-2.

But the situation changes to 4, which is itself a square number. Then the minimum number of numbers that make up his number is 1, which is himself.

After thinking for a while, it is actually a perfect square number of the previous topic gave a little thought, I forget exactly which one, anyway, is in the initialization can also be less than n of all the results of the square number are set to 1.

To this topic is already relatively obvious, the initialization is solved, the current results of how to derive from the previous results are also solved (state transfer).

Code 1

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 1; i*i <= n; i++) {
            dp[i*i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.min(dp[i], dp[j] + dp[i-j]);
            }
        }
        return dp[n];
    }
}

Code 2

This is a writeup I saw after I submitted my code, and it was much faster than mine. I then pondered this way he wrote it.

First of all, he doesn't need to initialize every square number, he can get it directly during the state transfer process.

What is clever is that he uses the value dp0, and he only looks at the results related to the square numbers, because we can deduce that the results should be added out of some large square numbers (as opposed to all adding one), so we can only look at the results related to them.

In the code dp[i - j * j] + 1, the plus one is actually the result of j*j in i - j * j, which is 1.

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

10K's