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

LeetCode Solutions

799. Champagne Tower

Time: $O(|\texttt{query_row}|^2)$

Space: $O(n^2)$

			


class Solution {
 public:
  double champagneTower(int poured, int query_row, int query_glass) {
    vector<vector<double>> dp(query_row + 1, vector<double>(query_row + 1));
    dp[0][0] = poured;

    for (int i = 0; i < query_row; ++i)
      for (int j = 0; j <= i; ++j)
        if (dp[i][j] > 1) {
          dp[i + 1][j] += (dp[i][j] - 1) / 2.0;
          dp[i + 1][j + 1] += (dp[i][j] - 1) / 2.0;
        }

    return min(1.0, dp[query_row][query_glass]);
  }
};




			


class Solution {
  public double champagneTower(int poured, int query_row, int query_glass) {
    double[][] dp = new double[query_row + 1][query_row + 1];
    dp[0][0] = poured;

    for (int i = 0; i < query_row; ++i)
      for (int j = 0; j <= i; ++j)
        if (dp[i][j] > 1) {
          dp[i + 1][j] += (dp[i][j] - 1) / 2.0;
          dp[i + 1][j + 1] += (dp[i][j] - 1) / 2.0;
        }

    return Math.min(1.0, dp[query_row][query_glass]);
  }
}




			


class Solution {
 public:
  double champagneTower(int poured, int query_row, int query_glass) {
    vector<double> dp(query_row + 1);
    dp[0] = poured;

    for (int i = 0; i < query_row; ++i) {
      vector<double> newDp(query_row + 1);
      for (int j = 0; j <= i; ++j)
        if (dp[j] > 1) {
          newDp[j] += (dp[j] - 1) / 2.0;
          newDp[j + 1] += (dp[j] - 1) / 2.0;
        }
      dp = move(newDp);
    }

    return min(1.0, dp[query_glass]);
  }
};