Skip to content

651. 4 Keys Keyboard 👍

Approach 1: Top-down

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  int maxA(int n) {
    int ans = n;

    for (int i = 1; i <= n - 3; ++i)
      ans = max(ans, maxA(i) * (n - 1 - i));

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
  public int maxA(int n) {
    int ans = n;

    for (int i = 1; i <= n - 3; ++i)
      ans = Math.max(ans, maxA(i) * (n - 1 - i));

    return ans;
  }
}

Approach 2: Bottom-up

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int maxA(int n) {
    // dp[i] := the maximum 'A' can be printed with i pressings
    vector<int> dp(n + 1);

    // 'A' * i
    iota(dp.begin(), dp.end(), 0);

    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= i - 3; ++j)
        dp[i] = max(dp[i], dp[j] * (i - j - 1));

    return dp[n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int maxA(int n) {
    // dp[i] := the maximum 'A' can be printed with i pressings
    int[] dp = new int[n + 1];

    for (int i = 0; i <= n; ++i) {
      dp[i] = i; // 'A' * i
      for (int j = 0; j <= i - 3; ++j)
        dp[i] = Math.max(dp[i], dp[j] * (i - j - 1));
    }

    return dp[n];
  }
}