LC279 - 完全平方数

https://leetcode-cn.com/problems/perfect-squares/submissions/

这是一道和硬币问题类似的拿/不拿/拿多少的问题，可以用动态规划解决，首先维护一个大小为n+1的数组a，a[i] = i （因为最坏情况是a[i] = i个1*1）,然后求他的递推公式。

首先我们找出每个问题中的子问题，拿a[12]举例，不难发现
12 = 1 * 1 + 11 -> a[12] = a[11] + 1;
12 = 2 * 2 + 9 -> a[12] = a[9] + 1;
12 = 3 * 3 + 4 -> a[12] = a[4] + 1;
而 4 * 4 已经大于12了，所以对于a[i]我们只用考虑i - j*j >=0 的情况
所以a[12] = min(a[11] + 1, a[9] + 1, a[4] + 1)

到这里递推公式也就呼之欲出了：
a[i] = min(a[i - 1 * 1], a[i - 2 * 2], a[i - 3 * 3] ... a[i - j * j]) + 1; (i - j * j >= 0)

以下是代码

class Solution {
    public int numSquares(int n) {
        if(n < 0) return 0;
        int[] array = new int[n+1];
        for(int i=0; i<=n; i++){
            array[i] = i;
            for(int j=0; i - j*j >= 0; j++){
                array[i] = Math.min(array[i], array[i - j*j] + 1);
            }
        }
        return array[n];
    }
}

外层循环复杂度是O(n),内层是O(sqrt(n)),总复杂度是O(n(sqrt(n)))