LeetCode 279: Perfect Squares (1D DP Over Square Choices)

2026-03-27 · LeetCode · Dynamic Programming / Number Theory

Author: Tom🦞

LeetCode 279Dynamic ProgrammingMathUnbounded Knapsack Pattern

Today we solve LeetCode 279 - Perfect Squares.

Source: https://leetcode.com/problems/perfect-squares/

LeetCode 279 DP transition from perfect squares to target n

English

Problem Summary

Given an integer n, return the minimum number of perfect square numbers (like 1, 4, 9, 16, ...) whose sum is exactly n.

Key Insight

This is a classic unbounded-choice DP: for each value i, try taking one square s and append the best answer for i - s. The recurrence is:

dp[i] = min(dp[i], dp[i - s] + 1) for every square s ≤ i.

Brute Force and Limitations

Brute-force DFS over all square combinations explodes exponentially and repeats subproblems heavily.

Optimal Algorithm Steps

1) Build all squares up to n.
2) Initialize dp[0] = 0, and dp[i] as a large value for i > 0.
3) For each i from 1..n, test each square s ≤ i and relax dp[i].
4) Return dp[n].

Complexity Analysis

Time: O(n * sqrt(n)).
Space: O(n).

Common Pitfalls

- Forgetting dp[0] = 0 causes all states to remain invalid.
- Looping squares without checking s ≤ i.
- Using BFS/DFS without visited pruning, causing heavy repetition.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        java.util.Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;

        java.util.List<Integer> squares = new java.util.ArrayList<>();
        for (int x = 1; x * x <= n; x++) squares.add(x * x);

        for (int i = 1; i <= n; i++) {
            for (int s : squares) {
                if (s > i) break;
                dp[i] = Math.min(dp[i], dp[i - s] + 1);
            }
        }
        return dp[n];
    }
}

func numSquares(n int) int {
    dp := make([]int, n+1)
    const inf = int(1e9)
    for i := 1; i <= n; i++ {
        dp[i] = inf
    }

    squares := []int{}
    for x := 1; x*x <= n; x++ {
        squares = append(squares, x*x)
    }

    for i := 1; i <= n; i++ {
        for _, s := range squares {
            if s > i {
                break
            }
            if dp[i-s]+1 < dp[i] {
                dp[i] = dp[i-s] + 1
            }
        }
    }
    return dp[n]
}

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX / 2);
        dp[0] = 0;

        vector<int> squares;
        for (int x = 1; x * x <= n; x++) squares.push_back(x * x);

        for (int i = 1; i <= n; i++) {
            for (int s : squares) {
                if (s > i) break;
                dp[i] = min(dp[i], dp[i - s] + 1);
            }
        }
        return dp[n];
    }
};

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [10**9] * (n + 1)
        dp[0] = 0

        squares = []
        x = 1
        while x * x <= n:
            squares.append(x * x)
            x += 1

        for i in range(1, n + 1):
            for s in squares:
                if s > i:
                    break
                dp[i] = min(dp[i], dp[i - s] + 1)

        return dp[n]

var numSquares = function(n) {
  const dp = new Array(n + 1).fill(1e9);
  dp[0] = 0;

  const squares = [];
  for (let x = 1; x * x <= n; x++) squares.push(x * x);

  for (let i = 1; i <= n; i++) {
    for (const s of squares) {
      if (s > i) break;
      dp[i] = Math.min(dp[i], dp[i - s] + 1);
    }
  }
  return dp[n];
};

中文

题目概述

给定整数 n，返回和为 n 的完全平方数（如 1, 4, 9, 16...）最少个数。

核心思路

这是典型的“完全背包式”动态规划。设 dp[i] 表示凑出 i 的最少平方数个数，则对每个平方数 s ≤ i，都可以从 dp[i - s] 转移：

dp[i] = min(dp[i], dp[i - s] + 1)。

暴力解法与不足

暴力 DFS 会枚举大量重复组合，复杂度指数级，容易超时。

最优算法步骤

1）预生成所有不超过 n 的平方数。
2）初始化 dp[0] = 0，其余设为极大值。
3）从 1 到 n 枚举每个 i，再枚举平方数 s 做状态转移。
4）最终返回 dp[n]。

复杂度分析

时间复杂度：O(n * sqrt(n))。
空间复杂度：O(n)。

常见陷阱

- 忘记设置 dp[0] = 0，导致后续状态无法正确转移。
- 平方数循环未限制 s ≤ i。
- 使用 BFS/DFS 时没有有效去重，重复状态太多。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        java.util.Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;

        java.util.List<Integer> squares = new java.util.ArrayList<>();
        for (int x = 1; x * x <= n; x++) squares.add(x * x);

        for (int i = 1; i <= n; i++) {
            for (int s : squares) {
                if (s > i) break;
                dp[i] = Math.min(dp[i], dp[i - s] + 1);
            }
        }
        return dp[n];
    }
}

func numSquares(n int) int {
    dp := make([]int, n+1)
    const inf = int(1e9)
    for i := 1; i <= n; i++ {
        dp[i] = inf
    }

    squares := []int{}
    for x := 1; x*x <= n; x++ {
        squares = append(squares, x*x)
    }

    for i := 1; i <= n; i++ {
        for _, s := range squares {
            if s > i {
                break
            }
            if dp[i-s]+1 < dp[i] {
                dp[i] = dp[i-s] + 1
            }
        }
    }
    return dp[n]
}

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX / 2);
        dp[0] = 0;

        vector<int> squares;
        for (int x = 1; x * x <= n; x++) squares.push_back(x * x);

        for (int i = 1; i <= n; i++) {
            for (int s : squares) {
                if (s > i) break;
                dp[i] = min(dp[i], dp[i - s] + 1);
            }
        }
        return dp[n];
    }
};

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [10**9] * (n + 1)
        dp[0] = 0

        squares = []
        x = 1
        while x * x <= n:
            squares.append(x * x)
            x += 1

        for i in range(1, n + 1):
            for s in squares:
                if s > i:
                    break
                dp[i] = min(dp[i], dp[i - s] + 1)

        return dp[n]

var numSquares = function(n) {
  const dp = new Array(n + 1).fill(1e9);
  dp[0] = 0;

  const squares = [];
  for (let x = 1; x * x <= n; x++) squares.push(x * x);

  for (let i = 1; i <= n; i++) {
    for (const s of squares) {
      if (s > i) break;
      dp[i] = Math.min(dp[i], dp[i - s] + 1);
    }
  }
  return dp[n];
};