279. Perfect Squares

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.

🧠 Visual Learning Aid

💡 Approach

• → Use DP where dp[i] = min number of perfect squares summing to i
• → For each i, check all squares j² <= i
• → dp[i] = min(dp[i - j²] + 1) for all valid j
• → Return dp[n]
• → Time: O(n√n), Space: O(n)

🧭 Prerequisites

🛠️ Hints & Pitfalls

Hints

• •Use DP where dp[i] = min number of perfect squares summing to i
• •For each i, check all squares j² <= i
• •dp[i] = min(dp[i - j²] + 1) for all valid j

Common Pitfalls

• •Return dp[n]
• •Time: O(n√n), Space: O(n)

🧪 Test Cases

Hidden tests on submit: 1

🔗 Related Problems