279. Perfect Squares

发表于 | 分类于 | 阅读次数

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

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
虽然不难，我放到这里的目的只是想说我分别用DFS，BFS，DP来解决这道题，但是DP终归是王道…

DFS

看到这道题，我想起了背包，但是没有想起背包问题肯定是dp解的，然后直接想到的就是DFS，用一个for循环，每次从后向前遍历，满足就继续遍历，跳出条件是结果为0。
具体的，我先统计小于n的平方数，然后将n，list，number放到dfs的函数中，number就是走得步数；设置一个全局变量，当结果减为0后，判断number和res中最小的，赋值给res。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static int res=Integer.MAX_VALUE;
public static int numSquares(int n) {
    List<Integer> list=new ArrayList<>();
    int temp=1;
    for (int i=1;temp<=n;){
        list.add(temp);
        ++i;
        temp=i*i;
    }
    numSquares(list,n,0);
    return res;
}
private static void numSquares(List<Integer> list, int n, int number) {
    if(n==0){
        res=Math.min(res,number);
        return;
    }
    for(int i=list.size()-1;i>=0;i--){
        if(n<list.get(i))continue;
        numSquares(list,n-list.get(i),number+1);
    }
}

这个代码放到leetcode上，才过了48个test就超时了，48/586
举个例子：

1
2
3
4
5
6
7
8
9
以12为例
list={1，4，9}
12-9=3,3-1=2,2-1=1,1-1=0; number=4,res=4
12-4=8,8-4=4,4-4=0; number=3,res=3
12-1=11,11-9=2,2-1=1,1-1=0; number=4,res=3
12-1=11,11-4=7,7-4=3,3-1=2,2-1=1,1-1=0; number=6,res=3;
12-1=11,11-4=7,7-1=6,...
...
12-1=11,11-1=10,10-1=9,9-1=8,...1-1=0; number=12,res=3;

可以看到当n=12时，就有很多种可能，而且显然后面的情况根本就不用计算，我就想给一个判断，当number大于当前res时，就不用再dfs了，因为该路径的长度肯定超出，于是想到了BFS，BFS可以计算最短路径，见下面。

BFS

BFS的核心就是使用队列，每个方向走一步，然后判断各方向是否达到了终点，到达终点就返回。
这里我用两个变量记录，一个变量表示上一步的要遍历的个数，一个变量代表当前步遍历的个数，当n=0的时候，肯定是最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int numSquares(int n) {
    List<Integer> list=new ArrayList<>();
    Queue<Integer> queue=new LinkedList<>();
    int k1,k2=0,res=0;
    int temp=1;
    for (int i=1;temp<=n;){
        list.add(temp);
        ++i;
        temp=i*i;
    }
    queue.add(n);
    k1=1;
    while (!queue.isEmpty()){
        n=queue.poll();
        if(n==0)return res;
        for(int i=list.size()-1;i>=0;i--){
            if(n<list.get(i))continue;
            if(n-list.get(i)==0)return res+1;
            queue.add(n-list.get(i));
            k2++;
        }
        k1--;
        if(k1==0){k1=k2;k2=0;res++;}
    }
    return -1;
}

这样就在leetcode上通过了，beats 35.06%
举个例子：

1
2
3
4
5
6
7
以12为例
list={1，4，9}
queue={12}
第一步分别用出列元素减list中的元素：queue={3,8,11}
第二步继续用上一步的三个方向继续向下遍历，可以得到第二步后的结果：queue={2,4,2,7,10}
第三步同上：queue={1,0,3,1,3,6,1,6,8}
这里出现了0，返回步数3

上面还有什么问题呢，我们注意看第二步，queue中有两个2，这样显然会重复计算，那么怎么解决呢，怎么优化呢，只能用DP了，见下面。

DP

DP的解法总是让人惊奇，用dp[i]表示n=i的时候，需要的最小步数，有如下通项公式：

就是当n=i，然后遍历所有的可能，找出n=i的最小步数赋值给dp[i]，代码如下：

1
2
3
4
5
6
7
8
9
10
11
public static int numSquares2(int n) {
    int dp[]=new int[n+1];
    for(int i=0;i<dp.length;i++)dp[i]=Integer.MAX_VALUE;
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j*j<=i;j++){
            dp[i]=Math.min(dp[i],dp[i-j*j]+1);
        }
    }
    return dp[n];
}

leetcode 上betas 72.43%
举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
以12为例
dp[0]=0
dp[1]=dp[0]+1=1
dp[2]=dp[1]+1=2
dp[3]=dp[2]+1=3
dp[4]=dp[0]+1=1
dp[5]=dp[4]+1=2
dp[6]=dp[5]+1=3
dp[7]=dp[6]+1=4
dp[8]=dp[4]+1=2
dp[9]=dp[0]+1=1
dp[10]=dp[9]+1=2
dp[11]=dp[10]+1=3
dp[12]=dp[8]+1=3

好了，到这里就结束了，不过如果想继续研究，我们看上面的结果会发现一些数学规律，然后用这个规律也可以解决本问题，这里就不深入了。

如果觉得有帮助，给我打赏吧！