279. 完全平方数

题目描述

如果一个整数等于某个整数的平方，就称它是完全平方数，例如 1、4、9、16；而 3、11 不是。

输入一个正整数 n。要把 n 写成若干个完全平方数之和，同一个平方数可以使用多次。返回所用平方数个数的最小值。

示例 1

输入：n = 12
输出：3

解释：12 = 4 + 4 + 4，至少需要 3 个。

示例 2

输入：n = 13
输出：2

解释：13 = 4 + 9，至少需要 2 个。

数据范围

1 <= n <= 10^4

解题思路：完全背包动态规划

dp[x] 表示凑出 x 的最少个数，枚举最后添加的平方数。

为什么正确

计算 dp[x] 时，所有 dp[x-square] 已经是最优值。

复杂度分析

时间 O(n√n)，空间 O(n)。

易错点

完全平方数可以重复使用，所以每个 x 都应从更小的 dp 状态转移。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] + [n + 1] * n
        for x in range(1, n + 1):
            square = 1
            while square * square <= x:
                dp[x] = min(dp[x], dp[x - square * square] + 1)
                square += 1
        return dp[n]

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; Arrays.fill(dp, n + 1); dp[0] = 0;
        for (int x = 1; x <= n; x++) {
            int square = 1;
            while (square * square <= x) {
                dp[x] = Math.min(dp[x], dp[x - square * square] + 1);
                square += 1;
            }
        }
        return dp[n];
    }
}

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, n + 1); dp[0] = 0;
        for (int x = 1; x <= n; x++) {
            int square = 1;
            while (square * square <= x) {
                dp[x] = min(dp[x], dp[x - square * square] + 1);
                square += 1;
            }
        }
        return dp[n];
    }
};

func numSquares(n int) int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = n + 1
    }
    for x := 1; x <= n; x++ {
        square := 1
        for square*square <= x {
            dp[x] = min(dp[x], dp[x-square*square]+1)
            square += 1
        }
    }
    return dp[n]
}

var numSquares = function(n) {
    const dp = Array(n + 1).fill(n + 1); dp[0] = 0;
    for (let x = 1; x <= n; x++) {
        let square = 1;
        while (square * square <= x) {
            dp[x] = Math.min(dp[x], dp[x - square * square] + 1);
            square += 1;
        }
    }
    return dp[n];
};

function numSquares(n: number): number {
    const dp: number[] = Array(n + 1).fill(n + 1); dp[0] = 0;
    for (let x = 1; x <= n; x++) {
        let square = 1;
        while (square * square <= x) {
            dp[x] = Math.min(dp[x], dp[x - square * square] + 1);
            square += 1;
        }
    }
    return dp[n];
};

载入编辑器，自己跑一遍 →

其他解法

动态规划和 BFS 都是通用的“最少个数”解法：DP 按金额顺序填表，BFS 按个数分层扩展并在到达 0 时提前停止。四平方和定理直接把答案限定在 1–4，逐一判断，最快但只适用于平方数。

解法 2：广度优先搜索时间 O(n√n)，空间 O(n)

把 0 到 n 的每个整数看成图上的点，从 x 减去一个完全平方数得到的数之间连一条边。从 n 出发做 BFS，第一次到达 0 时的层数就是最少的平方数个数。已访问的数不再入队。

把“最少个数”看成无权图最短路，答案很小（最多 4）时只搜索很少几层，实际通常比 DP 快。需要队列和访问数组。

class Solution:
    def numSquares(self, n: int) -> int:
        squares = []
        i = 1
        while i * i <= n:
            squares.append(i * i)
            i += 1
        visited = [False] * (n + 1)
        visited[n] = True
        level = [n]
        steps = 0
        while level:
            steps += 1
            nxt = []
            for x in level:
                for sq in squares:
                    y = x - sq
                    if y < 0:
                        break
                    if y == 0:
                        return steps
                    if not visited[y]:
                        visited[y] = True
                        nxt.append(y)
            level = nxt
        return steps

class Solution {
    public int numSquares(int n) {
        boolean[] visited = new boolean[n + 1];
        visited[n] = true;
        List<Integer> level = new ArrayList<>();
        level.add(n);
        int steps = 0;
        while (!level.isEmpty()) {
            steps++;
            List<Integer> nxt = new ArrayList<>();
            for (int x : level) {
                for (int i = 1; i * i <= x; i++) {
                    int y = x - i * i;
                    if (y == 0) return steps;
                    if (!visited[y]) {
                        visited[y] = true;
                        nxt.add(y);
                    }
                }
            }
            level = nxt;
        }
        return steps;
    }
}

class Solution {
public:
    int numSquares(int n) {
        vector<char> visited(n + 1, 0);
        visited[n] = 1;
        vector<int> level{n};
        int steps = 0;
        while (!level.empty()) {
            steps++;
            vector<int> nxt;
            for (int x : level) {
                for (int i = 1; i * i <= x; i++) {
                    int y = x - i * i;
                    if (y == 0) return steps;
                    if (!visited[y]) {
                        visited[y] = 1;
                        nxt.push_back(y);
                    }
                }
            }
            level.swap(nxt);
        }
        return steps;
    }
};

func numSquares(n int) int {
	visited := make([]bool, n+1)
	visited[n] = true
	level := []int{n}
	steps := 0
	for len(level) > 0 {
		steps++
		nxt := []int{}
		for _, x := range level {
			for i := 1; i*i <= x; i++ {
				y := x - i*i
				if y == 0 {
					return steps
				}
				if !visited[y] {
					visited[y] = true
					nxt = append(nxt, y)
				}
			}
		}
		level = nxt
	}
	return steps
}

var numSquares = function(n) {
    const visited = new Uint8Array(n + 1);
    visited[n] = 1;
    let level = [n];
    let steps = 0;
    while (level.length) {
        steps++;
        const nxt = [];
        for (const x of level) {
            for (let i = 1; i * i <= x; i++) {
                const y = x - i * i;
                if (y === 0) return steps;
                if (!visited[y]) {
                    visited[y] = 1;
                    nxt.push(y);
                }
            }
        }
        level = nxt;
    }
    return steps;
};

function numSquares(n: number): number {
    const visited = new Uint8Array(n + 1);
    visited[n] = 1;
    let level: number[] = [n];
    let steps = 0;
    while (level.length) {
        steps++;
        const nxt: number[] = [];
        for (const x of level) {
            for (let i = 1; i * i <= x; i++) {
                const y = x - i * i;
                if (y === 0) return steps;
                if (!visited[y]) {
                    visited[y] = 1;
                    nxt.push(y);
                }
            }
        }
        level = nxt;
    }
    return steps;
}

解法 3：四平方和定理时间 O(√n)，空间 O(1)

拉格朗日四平方和定理：任何正整数都能表示成至多 4 个平方数之和。勒让德三平方和定理：n 需要 4 个当且仅当 n = 4^a(8b+7)。依次判断：n 是平方数返回 1；满足 4^a(8b+7) 返回 4；枚举 i 看 n - i² 是否为平方数，是则返回 2；否则返回 3。

最快，只要 O(√n) 且不占额外空间。依赖数论定理，面试中难以现场推出，也不能推广到其他“最少硬币”类问题。

class Solution:
    def numSquares(self, n: int) -> int:
        def is_square(x):
            r = int(x ** 0.5)
            while r * r > x:
                r -= 1
            while (r + 1) * (r + 1) <= x:
                r += 1
            return r * r == x

        if is_square(n):
            return 1
        m = n
        while m % 4 == 0:
            m //= 4
        if m % 8 == 7:
            return 4
        i = 1
        while i * i < n:
            if is_square(n - i * i):
                return 2
            i += 1
        return 3

class Solution {
    private boolean isSquare(int x) {
        int r = (int) Math.sqrt(x);
        while (r * r > x) r--;
        while ((r + 1) * (r + 1) <= x) r++;
        return r * r == x;
    }

    public int numSquares(int n) {
        if (isSquare(n)) return 1;
        int m = n;
        while (m % 4 == 0) m /= 4;
        if (m % 8 == 7) return 4;
        for (int i = 1; i * i < n; i++)
            if (isSquare(n - i * i)) return 2;
        return 3;
    }
}

class Solution {
    bool isSquare(int x) {
        int r = (int)sqrt((double)x);
        while (r * r > x) r--;
        while ((r + 1) * (r + 1) <= x) r++;
        return r * r == x;
    }

public:
    int numSquares(int n) {
        if (isSquare(n)) return 1;
        int m = n;
        while (m % 4 == 0) m /= 4;
        if (m % 8 == 7) return 4;
        for (int i = 1; i * i < n; i++)
            if (isSquare(n - i * i)) return 2;
        return 3;
    }
};

func numSquares(n int) int {
	isSquare := func(x int) bool {
		r := int(math.Sqrt(float64(x)))
		for r*r > x {
			r--
		}
		for (r+1)*(r+1) <= x {
			r++
		}
		return r*r == x
	}
	if isSquare(n) {
		return 1
	}
	m := n
	for m%4 == 0 {
		m /= 4
	}
	if m%8 == 7 {
		return 4
	}
	for i := 1; i*i < n; i++ {
		if isSquare(n - i*i) {
			return 2
		}
	}
	return 3
}

var numSquares = function(n) {
    const isSquare = (x) => {
        const r = Math.round(Math.sqrt(x));
        return r * r === x;
    };
    if (isSquare(n)) return 1;
    let m = n;
    while (m % 4 === 0) m /= 4;
    if (m % 8 === 7) return 4;
    for (let i = 1; i * i < n; i++)
        if (isSquare(n - i * i)) return 2;
    return 3;
};

function numSquares(n: number): number {
    const isSquare = (x: number): boolean => {
        const r = Math.round(Math.sqrt(x));
        return r * r === x;
    };
    if (isSquare(n)) return 1;
    let m = n;
    while (m % 4 === 0) m /= 4;
    if (m % 8 === 7) return 4;
    for (let i = 1; i * i < n; i++)
        if (isSquare(n - i * i)) return 2;
    return 3;
}

动态规划专题的其他题目

查看动态规划全部题目 →