## 651. 4 Keys Keyboard

Imagine you have a special keyboard with the following keys:

`Key 1: (A)`

: Print one 'A' on screen.

`Key 2: (Ctrl-A)`

: Select the whole screen.

`Key 3: (Ctrl-C)`

: Copy selection to buffer.

`Key 4: (Ctrl-V)`

: Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for **N** times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.

**Example 1:**

Input:N = 3Output:3Explanation:We can at most get 3 A's on screen by pressing following key sequence: A, A, A

**Example 2:**

Input:N = 7Output:9Explanation:We can at most get 9 A's on screen by pressing following key sequence: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

**Note:**

- 1 <= N <= 50
- Answers will be in the range of 32-bit signed integer.

## Rust Solution

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

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