Question

651. 四个键的键盘

English Version

题目描述

假设你有一个特殊的键盘包含下面的按键：

• A：在屏幕上打印一个 'A'。
• Ctrl-A：选中整个屏幕。
• Ctrl-C：复制选中区域到缓冲区。
• Ctrl-V：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。

现在，_你可以 最多 按键 n 次（使用上述四种按键），返回屏幕上最多可以显示 'A' 的个数 _。

 

示例 1:

输入: n = 3
输出: 3
解释: 
我们最多可以在屏幕上显示三个'A'通过如下顺序按键：
A, A, A

示例 2:

输入: n = 7
输出: 9
解释: 
我们最多可以在屏幕上显示九个'A'通过如下顺序按键：
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

 

提示:

• 1 <= n <= 50

解法

方法一：动态规划

定义 $dp[i]$ 表示前 $i$ 个按键可以显示的最大个数。

我们可以发现，要显示最多的 A，要么一直按 A，要么以 Ctrl-V 结束。

• 一直按 A 的情况，满足 $dp[i] = i$。
• 以 Ctrl-V 结束的情况，我们枚举对应的 Ctrl-A 的位置 $j$，可以得到 $dp[i]=max(dp[i], dp[j-1] \times (i - j))$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

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]
}