## 650. 2 Keys Keyboard

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

`Copy All`

: You can copy all the characters present on the notepad (partial copy is not allowed).`Paste`

: You can paste the characters which are copied**last time**.

Given a number `n`

. You have to get **exactly** `n`

'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get `n`

'A'.

**Example 1:**

Input:3Output:3Explanation:Intitally, we have one character 'A'. In step 1, we useCopy Alloperation. In step 2, we usePasteoperation to get 'AA'. In step 3, we usePasteoperation to get 'AAA'.

**Note:**

- The
`n`

will be in the range [1, 1000].

## Rust Solution

```
struct Solution;
impl Solution {
fn min_steps(n: i32) -> i32 {
let n = n as usize;
let mut dp = vec![0; n + 1];
for i in 2..=n {
dp[i] = i;
for j in (2..i).rev() {
if i % j == 0 {
dp[i] = dp[j] + i / j;
break;
}
}
}
dp[n] as i32
}
}
#[test]
fn test() {
let n = 3;
let res = 3;
assert_eq!(Solution::min_steps(n), res);
}
```

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