Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

651. 4 Keys Keyboard

Time: $O(N^2)$

Space: $O(N)$

			


class Solution {
 public:
  int maxA(int N) {
    int ans = N;

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

    return ans;
  }
};




			


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 - i - 1));

    return ans;
  }
}




			


class Solution {
 public:
  int maxA(int N) {
    // dp[i] := max 'A' can be printed w/ i pressings
    vector<int> dp(N + 1);

    // 'A' * i
    iota(begin(dp), end(dp), 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];
  }
};