276-Paint-Fence

原题链接

0x0 题目详情

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

0x1 解题思路

我一开始思考的是将n每次都分为两个数n1和n2,再递归判断n1和n2拆解后的最小平方个数,但是时间爆炸。

后来采取评论区的一种思路: 我们将n每次减去一个平方数,查看剩余值需要分解为多少个平方数,速度提升很明显。因为少判断了左边的数需要拆解的个数。

dp数组的初始化比较简单,但是仍需注意,应该将dp[i]初始化为i,因为对于要给数i,最多拆解成i个1。

0x2 代码实现

原始思路,将n拆解为两个数,注释部分为原始递归代码:

class Solution {
    public int numSquares(int n) {
        if(n<2){
            return 1;
        }
        return recur(n);

    }
    //返回将number拆成完全平凡数需要的个数
    private int recur(int number){
        int[] dp=new int[number+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=number;i++){
            int n=i;
            for(int j=1;n>0;j+=2){
                n-=j;
            }
            if(n==0){
                dp[i]=1;
                continue;
            }
            dp[i]=Integer.MAX_VALUE;
            for(int j=1;j<=i/2;j++){
                dp[i]=Math.min(dp[i],dp[j]+dp[i-j]);
            }
        }
        return dp[number];
        // if(number<2){
        //     return 1;
        // }

        // for(int i=1;n>0;i+=2){
        //     n-=i;
        // }
        // if(n==0){
        //     return 1;
        // }
        // int result=Integer.MAX_VALUE;
        // for(int i=1;i<=number/2;i++){
        //     result=Math.min(result,recur(i)+recur(number-i));
        // }
        // return result;
    }
}

优化代码:

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) { 
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
            }
        }
        return dp[n];
    }
}

0x3 课后总结

经典题目,熟悉技巧吧。其实还有一种使用数学公式的方法,因为一般都想不到,这里就不做过多描述。