aboutsummaryrefslogtreecommitdiff
path: root/perfect_squares.rs
blob: 3887e40b397899014cf4b548f0b4ddf58c2643b7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
use std::cmp::min;
struct Solution;

impl Solution {
    pub fn num_squares(n: i32) -> i32 {
        let mut dp: Vec<i32> = vec![std::i32::MAX; n as usize + 1];
        dp[0] = 0;
        for i in 1..(n as usize + 1) {
            let mut j: usize = 1;
            while j * j <= i {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
                j += 1;
            }
        }
        dp[n as usize]
    }
}

fn main() {
    print!("{}", Solution::num_squares(12));
}