aboutsummaryrefslogtreecommitdiff
path: root/perfect_squares.rs
diff options
context:
space:
mode:
Diffstat (limited to 'perfect_squares.rs')
-rw-r--r--perfect_squares.rs21
1 files changed, 21 insertions, 0 deletions
diff --git a/perfect_squares.rs b/perfect_squares.rs
new file mode 100644
index 0000000..3887e40
--- /dev/null
+++ b/perfect_squares.rs
@@ -0,0 +1,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));
+}