leetcode-完全平方数(279)

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

示例 1:

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

示例 2:

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

思路

假设dp[i]表示i对应的完全平方数，考虑dp[12];

那么

Case1 : dp[12] = dp[12-1]+1;

Case2 : dp[12]= dp[12-4]+1;

Case3 : dp[12]= dp[12-9]+1;

最终dp[12]= 3种case的最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int numSquares(int n) {
        ArrayList<Integer> al= new ArrayList();
        for(int i =1;i*i<=n;i++){
            al.add(i*i);
        }
        int [] dp = new int[n+1];
        dp[0]=0;
        for(int i =1;i<=n;i++){
            dp[i]=Integer.MAX_VALUE;
            for(int j =0;j<al.size();j++){
                int temp =al.get(j);
                if(temp>i){
                    break;
                }
                if(dp[i-temp]+1<dp[i]){
                    dp[i]=dp[i-temp]+1;
                }
            }
        }
        
        return dp[n];
    }
}