279. Perfect Squares

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Math、Dynamic Programming、Breadth-First Search

一、題目

Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

  • Input: n = 12
  • Output: 3
  • Explanation: 12 = 4 + 4 + 4

Example 2:

  • Input: n = 13
  • Output: 2
  • Explanation: 13 = 4 + 9

Constraints:

  • 1 <= n <= 10^4

二、分析

  • 動態規劃，令 dp[i] 為 n = i 時，由最少個 perfect squares 所組合成和為 i 的個數。
  • 當 n 為平方數時，dp[n] = 1。
  • 其餘則 `dp[n] = min(dp[n-i]+1, dp[i]);
    • dp[1] = 1，因為 1 為平方數
    • dp[2] = 2
    • dp[3] = 3
    • dp[4] = 1，因為 4 為平方數
    • dp[5] = 2，min(dp[4]+1, dp[1]+1)
    • dp[6] = 3，min(dp[5]+1, dp[2]+1)
    • dp[7] = 4，min(dp[6]+1, dp[3]+1)
    • dp[8] = 2，min(dp[7]+1, dp[4]+1)
    • dp[12] = 3, min(dp[12-1]+1, dp[12-4]+1, dp[12-9]+1)

三、解題

1. DP

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)
int numSquares(int n) {
    vector<int> dp(n+1, INT_MAX);
    vector<int> sel;
    for (int i = 1; i <= n; i++) {
        int x = sqrt(i);
        if (x*x == i) {     // 平方數時，增加選擇
            dp[i] = 1;
            sel.push_back(i);
        } else {
            for (int s : sel) {  // 動態規劃轉移方程
                dp[i] = min(dp[i-s]+1, dp[i]);
            }
        }
    }
    return dp[n];
}

回目錄 Catalog