279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

本题一开始想法是贪心算法，假设是12，我们直接取最靠近12的平方数，9，然后就剩3，继续取最靠近3的平方数，结果答案好像不太对。就明白不能用贪心。(看了看题解可以用贪心但不是这么用的)
从上面这个过程也不是一点都没获得，也可以看得出来这道题后面解其实可以通过前面的解来求得，那显然就用动归了。
状态转移方程就是dp[n] = min (dp[n - 1] +1,dp[n-4] +1, dp[n- 根号n]+1)
应该很显然，只要有了这个想法，写起代码来也是非常简单了。
代码如下:

class Solution {
    public int numSquares(int n) {
        
        int[] dp = new int [n+1];
        dp [0] = 0;

        for (int i = 1; i <= n; i++){
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= Math.sqrt(i); j++){
                int s = j * j;
                if (min > dp[i - s] + 1)  min = dp[i-s] + 1;
            }
            dp[i] = min;
        }
        return dp[n];
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。