Skip to content

799. Champagne Tower 👍

Approach 1: 2D DP

  • Time: $O(|\texttt{query_row}|^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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]);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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]);
  }
}

Approach 2: 1D DP

  • Time: $O(|\texttt{query_row}|^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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 = std::move(newDp);
    }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public double champagneTower(int poured, int query_row, int query_glass) {
    double[] dp = new double[query_row + 1];
    dp[0] = poured;

    for (int i = 0; i < query_row; ++i) {
      double[] newDp = new double[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 = newDp;
    }

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