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 = 3
Output: 3
Explanation: 
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:

Input: N = 7
Output: 9
Explanation: 
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. 1 <= N <= 50
  2. 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.