279. Perfect Squares

Description of Problem

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

Solution

Tags: Dynamic Programming

Explanation

We can solve the problem by the sub-problem. Consider the least number of perfect square numbers that sum to n. We can find *the least number of perfect square numbers that sum to n - 1*2, n - 2*2, n - 3*3, ...

\[ \begin{align} A[n] & = 0 & \text{if } n \le 0 \\ A[n] & = 1 + min_{j \in \lbrace 1,2,3,...\rbrace} \lbrace A[n - j^2] \rbrace & \text{otherwise} \end{align} \]

Code

impl Solution {
    pub fn num_squares(n: i32) -> i32 {
        let n = n as usize;
        let mut dp = vec![i32::MAX ; n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for target in 2..=n {
            for candidate in 1..{
                if target >= candidate * candidate {
                    dp[target] = dp[target].min(dp[target - candidate * candidate] + 1);
                }else {
                    break;
                }
            }
            
        }

        return dp[n] as i32;
    }
}

Complexity

Time Complexity

\(T(n) = \Theta(n^{3/2}) = \Theta(n^{1.5}) \)
- Iterate over the dp array
- The inner loop runs \(\sqrt{n}\) times.

Auxiliary Space

\(S(n) = O(n)\)

Leetbook