class Solution {
public:
int maxA(int n) {
}
};
651. 4键键盘
假设你有一个特殊的键盘包含下面的按键：
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相似题目
原站题解
golang 解法, 执行用时: 696 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-22 10:57:24
func max(a, b int) int {
if a < b {
return b
}
return a
}
func maxA(N int) int {
out := N
for i := 1; i < N-2; i++ {
out = max(out, maxA(i)*(N-1-i))
}
return out
}
python3 解法, 执行用时: 44 ms, 内存消耗: 16 MB, 提交时间: 2023-10-22 10:57:01
class Solution:
def maxA(self, n: int) -> int:
best = [0, 1]
for k in range(2, n+1):
best.append(max(best[x] * (k-x-1) for x in range(k-1)))
best[-1] = max(best[-1], best[-2] + 1) #addition
return best[n]
def maxA2(self, n: int) -> int:
best = [0, 1, 2, 3, 4, 5, 6, 9, 12,
16, 20, 27, 36, 48, 64, 81]
q = (n - 11) / 5 if n > 15 else 0
return best[n - 5*q] * 4**q
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.2 MB, 提交时间: 2023-10-22 10:55:32
class Solution {
public:
int maxA(int N) {
int dp[N+1];
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= N; i++) {
dp[i] = dp[i-1] + 1;
for(int j = 2; j < i; j++) {
dp[i] = max(dp[i], dp[j-2] * (i-j+1));
}
}
return dp[N];
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 38.1 MB, 提交时间: 2023-10-22 10:55:11
class Solution {
public int maxA(int n){
int[] dp = new int[n + 1];
for(int i = 1; i <= n; i++){
dp[i] = dp[i - 1] + 1;
for(int j = 2; j + 2 < i; j++){
dp[i] = Math.max(dp[i], dp[j] * (i - (j + 1)));
}
}
return dp[n];
}
}