###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 279. Perfect Squares

## [題目連結:] https://leetcode.com/problems/perfect-squares/description/

## 題目:
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.

## 解題想法:
* 題目為求n能用幾個perfect square構成
* ex: 12可以由
* 12個**1**
* 3個 **2** 構成

* DP:
* 定義: dp[i]
* **為正整數i最多要用幾個完全平方數才能湊出總和i**
* 初始: 每個N最多用n個完全平方數(n個1)
* 對於每個i
* 判斷j=1開始
* 若j * j <= i
* 則dp[i]=min(dp[i], dp[i-j * j]+1)
* 表示dp[i] 能繼承 dp[i-j * j ]的個數，再加上一個j，即可構成和為i

## Python:

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        #dp
        #每個N最多用n個完全平方數(n個1)
        #dp[i]為正整數i最多要用幾個完全平方數才能湊出總和i
        dp=[0]*(n+1)
        for i in range(n+1):
            dp[i]=i #初始最多用i個1合成
            j=1
            while j*j <= i:
                dp[i]=min(dp[i],dp[i-j*j]+1)
                j+=1
        return dp[n]

## C++:

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