难度: Medium
Submission
运行时间: 21 ms
内存: 16.0 MB
class Solution:
def maxA(self, n: int) -> int:
# dp[n] represent how many A can n ope can get
# choices: A CA CC CV
dp = [0 for i in range(n + 1)]
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + 1
for j in range(1, i - 2):
dp[i] = max(dp[i], dp[j - 1] * (i - (j + 1) + 1))
return dp[n]
Explain
这道题采用动态规划的思路求解。我们定义 `dp[n]` 表示 n 次操作能得到的最多 A 的数量。对于每个状态，我们有四种选择：输入 A、复制全部、粘贴、不操作。通过枚举这四种选择，取其中能得到最多 A 的选择作为当前状态的最优解。其中，如果选择复制全部，我们需要枚举复制的起点，即 dp[j-1]，其中 j 表示上一次复制全部的位置，然后将剪贴板中的内容粘贴 i-(j+1)+1 次，即可得到 dp[j-1] * (i-(j+1)+1) 个 A。最后返回 dp[n] 即可。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def maxA(self, n: int) -> int:
# dp[n] 表示 n 次操作能得到的最多 A 的数量
# 选择有四种：输入 A、复制全部、粘贴、不操作
dp = [0 for i in range(n + 1)]
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + 1 # 选择输入 A
for j in range(1, i - 2): # 枚举复制全部的起点
# 选择复制全部，然后粘贴 i-(j+1)+1 次
dp[i] = max(dp[i], dp[j - 1] * (i - (j + 1) + 1))
return dp[n]
Explore
在动态规划的解决方案中，选择从 `dp[i-1] + 1` 开始更新 `dp[i]` 是因为这是最基本的操作，即每次操作仅仅增加一个 'A'。这意味着每次迭代从最简单的操作（添加一个 'A'）开始，然后考虑更复杂的操作（如复制粘贴）。这样做确保了在每个步骤中，我们都从已知的最小操作（即前一步+1个A）开始计算，为后续可能的复制粘贴操作提供基线。
实际上，在这个问题的上下文中，选择“不操作”并不是一个有效的策略。提及到‘不操作’可能是在讨论操作的可选性时作为考虑的一部分，但在实现最大化输出的目标时，每一步都应该是有效的操作（输入A、复制或粘贴）。因此，在代码实现中，我们不会看到利用‘不操作’的代码，因为它不会增加产生的'A'的数量，不符合题目的最大化目标。
这个公式是基于复制粘贴操作的逻辑推导出来的。在这里，`dp[j-1]` 表示在第 `j-1` 次操作后，所能得到的最大'A'的数量。当在第 `j` 次操作选择复制全部时，从第 `j+1` 次开始到第 `i` 次操作，我们可以选择粘贴。因此，粘贴的次数是 `i - (j+1) + 1`，即从第 `j+1` 次到第 `i` 次的操作次数。因此，从第 `j-1` 次得到的字符数量被复制，然后在后续的每一次操作中被粘贴，所以最终得到的字符总数是 `dp[j-1]` 乘以粘贴次数 `i - (j+1) + 1`。这个公式是计算在选择在第 `j` 次操作后开始复制并粘贴到第 `i` 次所能得到的最大'A'的数量的方法。