Question

651. 4 Keys Keyboard

中文文档

Description

Imagine you have a special keyboard with the following keys:

• A: Print one 'A' on the screen.
• Ctrl-A: Select the whole screen.
• Ctrl-C: Copy selection to buffer.
• Ctrl-V: Print buffer on screen appending it after what has already been printed.

Given an integer n, return _the maximum number of _'A'_ you can print on the screen with at most _n_ presses on the keys_.

 

Example 1:

Input: n = 3
Output: 3
Explanation: We can at most get 3 A's on screen by pressing the 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

 

Constraints:

• 1 <= n <= 50

Solutions

Solution 1

class Solution:
  def maxA(self, n: int) -> int:
    dp = list(range(n + 1))
    for i in range(3, n + 1):
      for j in range(2, i - 1):
        dp[i] = max(dp[i], dp[j - 1] * (i - j))
    return dp[-1]

class Solution {
  public int maxA(int n) {
    int[] dp = new int[n + 1];
    for (int i = 0; i < n + 1; ++i) {
      dp[i] = i;
    }
    for (int i = 3; i < n + 1; ++i) {
      for (int j = 2; j < i - 1; ++j) {
        dp[i] = Math.max(dp[i], dp[j - 1] * (i - j));
      }
    }
    return dp[n];
  }
}

class Solution {
public:
  int maxA(int n) {
    vector<int> dp(n + 1);
    iota(dp.begin(), dp.end(), 0);
    for (int i = 3; i < n + 1; ++i) {
      for (int j = 2; j < i - 1; ++j) {
        dp[i] = max(dp[i], dp[j - 1] * (i - j));
      }
    }
    return dp[n];
  }
};

func maxA(n int) int {
  dp := make([]int, n+1)
  for i := range dp {
    dp[i] = i
  }
  for i := 3; i < n+1; i++ {
    for j := 2; j < i-1; j++ {
      dp[i] = max(dp[i], dp[j-1]*(i-j))
    }
  }
  return dp[n]
}