最少的完全平方数

struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param n int整型 
        * @return int整型
    */
    pub fn numSquares(&self, n: i32) -> i32 {
        // write code here
        let mut res = vec![0];
        for i in 1 ..= n {
            res.push(i);
            for j in 1 ..= i {
                if j * j <= i {
                    use std::cmp::min;
                    res[i as usize] = min(res[i as usize], res[(i - j * j) as usize] + 1);
                } else {
                    break;
                }
            }
        }
        res[n as usize]
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int numSquares(int n) {
        // write code here
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i =1;i*i<=n;i++){
            for(int j =1;j<=n;j++){
                if(j-i*i>=0){
                    dp[j] =min(dp[j-i*i]+1,dp[j]);
                }
            }
        }
        return dp[n];
    }
};