力扣(LeetCode)799. 香槟塔(C++)

动态规划

设 $i$ 是行 , $j$ 是列 ， $f[i][j]$ 表示经过杯子的酒量 ，初始 $f[0][0]=poured$ ， 为了理解，当做每个杯子有无限容量。
当香槟溢出时，$f[i][j]$ 保留自己的一杯 ， 则有 $f[i][j]-1$ 杯流到下一层 ，均分到 $f[i+1][j]$ 和 $f[i+1][j+1]$ ， 有状态转移方程

{ f [ i + 1 ] [ j ] = ( f [ i ] [ j ] − 1 ) / 2 f [ i + 1 ] [ j + 1 ] = ( f [ i ] [ j ] − 1 ) / 2

{f[i+1][j]=(f[i][j]−1)/2f[i+1][j+1]=(f[i][j]−1)/2​

朴素dp

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<vector<double>> f(query_row+1,vector<double>(query_row+1)) ;
        f[0][0] = (double)poured;//假设酒杯容量无限
        for(int i = 0;i<query_row;i++){
            for(int j = 0;j<=i;j++){
                if(f[i][j]>1){//大于1杯,溢出
                    f[i+1][j] += (f[i][j]-1)/2;
                    f[i+1][j+1] += (f[i][j]-1)/2;
                }
            }
        }
        return min(1.0,f[query_row][query_glass]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度 $O(n^2)$ ， $n$ 是 $query\_row$ 的长度 ， 状态转移的时间复杂度 $O(n^2)$ 。

空间复杂度 $O(n^2)$ ， $f$ 数组的空间复杂度 $O(n^2)$ 。

优化dp

由于每一行的香槟只与上一行有关，可以省略状态转移方程的第 $1$ 维 ， 又因为与上一行的最多两个状态有关， 用滚动数组保存上一行的状态。

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<double> f{(double)poured};
        for(int i = 0;i<query_row;i++){
            vector<double> nextf(i+2);//上一行有(i+1)个杯子,下一行比上一行多1个杯子
            for(int j = 0;j<i+1;j++){//下一行比上一行多1个杯子。
                if(f[j]>1){
                    nextf[j] += (f[j]-1)/2;
                    nextf[j+1] += (f[j]-1)/2;
                }
            }
            f = nextf;//保存上一行的杯子酒量
        }
        return min(1.0,f[query_glass]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度 $O(n^2)$ ， $n$ 是 $query\_row$ 的长度 ， 状态转移的时间复杂度 $O(n^2)$ 。

空间复杂度 $O(n)$ ， 滚动数组的空间复杂度 $O(n)$ 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC