Perfect Squares 513

Question

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example

Given n = 12, return 3 because 12 = 4 + 4 + 4

Given n = 13, return 2 because 13 = 4 + 9

Solution

这道题不难，但是想说清楚好难。。。

dp[i]表示i可以由多少个完全平方数加和得到的最小值。

1. 将小于n的完全平方数初始化为1，表示完全平方数可以由自己加和得到。

2. 因为所有的数都可以看成某个数加上一个完全平方数得到。因此i从0遍历到n，寻找i加上某个完全平方数的和小于等于n时的最小值。设当前数(i + j j)可以由i＋某个完全平方数a＝j j(j j<=n)得到，若dp[i]+dp[j j]（即得到i所需要的最小值＋得到j j所需要的最小值）小于dp[i + j j]（因为j也可以由另外一个数i'加上另外一个完全平方数a'得到），则更新dp[j]的值。

代码如下：

public class Solution {
    /**
     * @param n a positive integer
     * @return an integer
     */
    public int numSquares(int n) {
        // Write your code here
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for(int i = 0; i * i <= n; i++){
            dp[i * i] = 1;
        }

        for(int i = 0; i <= n; i++){
            for(int j = 0; i + j * j <= n; j++){
                dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j]);
            }
        }

        return dp[n];
    }
}