给定一个正整数n,请找出最少个数的完全平方数,使得这些完全平方数的和等于n。
完全平方指用一个整数乘以自己例如1*1,2*2,3*3等,依此类推。若一个数能表示成某个整数的平方的形式,则称这个数为完全平方数。例如:1,4,9,和16都是完全平方数,但是2,3,5,8,11等等不是
数据范围:
5
2
5=1+4
8
2
8=4+4
9
1
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] } }