【Leetcode 热题 100】279. 完全平方数

问题背景

给你一个整数 $n$，返回 和为 $n$ 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，$1,4,9$ 和 $16$ 都是完全平方数，而 $3$ 和 $11$ 不是。

数据约束

• $1\le n\le 10^4$

解题过程

动态规划，用两个状态：$i$ 表示当前枚举的完全平方数的算数平方根，$j$ 表示剩余的和。
这样一来，状态转移方程就可以表示为$dfs(i,j)=\{\begin{array}{ll}dfs(i-1,j)& j<i^2\\ min(dfs(i-1,j),dfs(j-i^2)+1)& j\le i^2\end{array}$。
递归入口 是 $dfs(\lfloor \sqrt{n}\rfloor ,n)$，表示初始枚举的最大数为 $\sqrt{n}$，剩余的和为 $n$。
递归边界 是 $dfs(0,0)=0$，表示没有剩余的数可选，且和刚好为零。

翻译成递推之后，由于计算时只用到前一个状态，记忆化数组可以去掉一个维度。
递推的计算可以放在静态代码块里，给所有测试用例公用。

具体实现

递归

class Solution {
    private static final int[][] memo = new int[110][10010];

    static {
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
    }

    public int numSquares(int n) {
        return dfs((int) Math.sqrt(n), n);        
    }

    private int dfs(int i, int j) {
        if (i == 0) {
            return j == 0 ? 0 : Integer.MAX_VALUE;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        if (j < i * i) {
            return memo[i][j] = dfs(i - 1, j);
        }
        return memo[i][j] = Math.min(dfs(i - 1, j), dfs(i, j - i * i) + 1); 
    }
}

递推

class Solution {
    private static final int MAX_N = 10000;
    private static final int[][] dp = new int[110][MAX_N + 1];

    static {
        Arrays.fill(dp[0], Integer.MAX_VALUE);
        dp[0][0] = 0;
        for (int i = 1; i * i <= MAX_N; i++) {
            for (int j = 0; j <= MAX_N; j++) {
                if (j < i * i) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - i * i] + 1);
                }
            }
        }
    }

    public int numSquares(int n) {
        return dp[(int) Math.sqrt(n)][n];    
    }
}

空间优化

class Solution {
    private static final int MAX_N = 10000;
    private static final int[] dp = new int[MAX_N + 1];

    static {
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i * i <= MAX_N; i++) {
            for (int j = i * i; j <= MAX_N; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
    }

    public int numSquares(int n) {
        return dp[n];    
    }
}