Leetcode 799. Champagne Tower

这道题的思路就是建一个二维dp[i][j]，代表i行j列接到的所有的水，同时这个杯子溢出来的水(dp[i][j]-1)会有一半分别灌入杯子[i][j]和[i][j+1]。最后[i][j]杯子里的水就是1（杯子灌满）或者dp[i][j]（所有接到的水）的较小值。

 

时间复杂度 O(n^2),n代表行数

 空间复杂度 O(n^2) 

class Solution {

public:

    double champagneTower(int poured, int query_row, int query_glass) {

        vector<vector<double>> received(101, vector<double>(101, 0));

        received[0][0] = poured;

        for (int i=0; i<received.size()-1; i++) {

            for (int j=0; j<=i; j++) {

                double overflow = (received[i][j] - 1)/2;

                if (overflow > 0){

                    received[i+1][j] += overflow;

                    received[i+1][j+1] += overflow;

                }

            }

        }

        return min(1.0, received[query_row][query_glass]);

    }

};