799.香槟塔

链接：799.香槟塔
难度：Medium
标签：动态规划
简介：现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（ i 和 j 都从 0 开始）。

题解 1 - cpp

• 编辑时间：2022-11-20
• 执行用时：12ms
• 内存消耗：13.7MB
• 编程语言：cpp
• 解法介绍：模拟。

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, 0.0));
        dp[0][0] = (double)poured;
        for (int i = 1; i <= query_row; i++) {
            if (dp[i - 1][0] > 1.0) dp[i][0] = dp[i][i] = (dp[i - 1][0] - 1) / 2;
            for (int j = 1; j < i; j++) {
                if (dp[i - 1][j - 1] > 1.0) dp[i][j] += (dp[i - 1][j - 1] - 1) / 2;
                if (dp[i - 1][j] > 1.0) dp[i][j] += (dp[i - 1][j] - 1) / 2;
            }
        }
        return min(1.0, dp[query_row][query_glass]);
    }
};

题解 2 - cpp

• 编辑时间：2022-11-20
• 执行用时：16ms
• 内存消耗：13.7MB
• 编程语言：cpp
• 解法介绍：模拟。

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, 0.0));
        dp[0][0] = (double)poured;
        for (int i = 0; i < query_row; i++) {
            for (int j = 0; j <= i; j++) {
                if (dp[i][j] <= 1.0) continue;
                double val = (dp[i][j] - 1) / 2;
                dp[i + 1][j] += val;
                dp[i + 1][j + 1] += val;
            }
        }
        return min(1.0, dp[query_row][query_glass]);
    }
};