## 1240. Tiling a Rectangle with the Fewest Squares

Given a rectangle of size `n` x `m`, find the minimum number of integer-sided squares that tile the rectangle.

Example 1:

```Input: n = 2, m = 3
Output: 3
Explanation: `3` squares are necessary to cover the rectangle.
`2` (squares of `1x1`)
`1` (square of `2x2`)```

Example 2:

```Input: n = 5, m = 8
Output: 5
```

Example 3:

```Input: n = 11, m = 13
Output: 6
```

Constraints:

• `1 <= n <= 13`
• `1 <= m <= 13`

## Rust Solution

``````struct Solution;

use std::collections::HashMap;

impl Solution {
fn tiling_rectangle(n: i32, m: i32) -> i32 {
let mut memo: HashMap<(i32, i32), i32> = HashMap::new();
Self::dp(n, m, &mut memo)
}
fn dp(n: i32, m: i32, memo: &mut HashMap<(i32, i32), i32>) -> i32 {
if n == m {
1
} else {
if let Some(&res) = memo.get(&(n, m)) {
return res;
}
let mut res = std::i32::MAX;

for i in 1..n {
res = res.min(Self::dp(i, m, memo) + Self::dp(n - i, m, memo));
}

for j in 1..m {
res = res.min(Self::dp(n, j, memo) + Self::dp(n, m - j, memo));
}

for i in 1..n - 1 {
for j in 1..m - 1 {
let a = Self::dp(i, j + 1, memo);
let b = Self::dp(i + 1, m - j - 1, memo);
let c = Self::dp(n - i, j, memo);
let d = Self::dp(n - i - 1, m - j, memo);
res = res.min(a + b + c + d + 1);
}
}
memo.insert((n, m), res);
res
}
}
}

#[test]
fn test() {
let n = 2;
let m = 3;
let res = 3;
assert_eq!(Solution::tiling_rectangle(n, m), res);
let n = 5;
let m = 8;
let res = 5;
assert_eq!(Solution::tiling_rectangle(n, m), res);
let n = 11;
let m = 13;
let res = 6;
assert_eq!(Solution::tiling_rectangle(n, m), res);
let n = 7;
let m = 6;
let res = 5;
assert_eq!(Solution::tiling_rectangle(n, m), res);
let n = 10;
let m = 9;
let res = 6;
assert_eq!(Solution::tiling_rectangle(n, m), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.