LeetCode：完全平方数【279】【DP】

题目描述

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

示例 1:

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

示例 2:

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

题目分析

　　动态规划真的是笔试过程中必不可少的题型。

　　如果我们想知道n=15的方法数，我们可以转换为求n=14的方法数、n=11的方法数、n=6的方法数,然后他们中间取最小值+1，即是15的方法数。

　　同样，n=14的方法数，是n=13、n=10、n=5中的最小值+1....这样我们可以使用动态规划来避免重复计算。

Java题解

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