799. 香槟塔

题目链接
思路：动态规划+模拟
分析：可以将杯子的容量先扩大，就是将当前层的杯子看成无限大的容量，装再多的水也不会溢出，然后再把容量缩小为1份玻璃杯的体积。
模拟：为了好模拟，先将poured这个数放到无限大，将poured杯的水全部倒入第一层的杯子里，那么第一个杯子装了poured杯的水，那么溢出的水也就是poured-1。
溢出到第二层，第二层的第一个杯子装的水就是(poured-1)/2，第二层的第二个杯子装的水也是(poured-1)/2。再分析每个杯子溢出的水，直到分析到题目要我们求得杯子，就完成了。
定义：dp[i][j]:表示第i行第j列杯子里的水量（可以大于1）
如果dp[i][j]>1，那么肯定是要溢出的，溢出的水的量就是dp[i][j]-1，溢出的水去向分别是dp[i+1][j]和dp[i+1][j+1]。这就是动态转移方程。
代码：

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        //dp[i][j]:表示第i行第j列杯子里的水量（可以大于1）
        double[][] dp = new double[query_row+2][query_row+2];
        //由上面分析的动态转移方程知，需要从前往后进行转移
        dp[0][0] = poured;
        for(int i=0; i<=query_row; i++){
            for(int j=0; j<=i; j++){
                if(dp[i][j]<=1){
                	//不会溢出
                    continue;
                }
                //溢出，溢出的水只有两个去向
                dp[i+1][j] += (dp[i][j]-1)/2;
                dp[i+1][j+1] += (dp[i][j]-1)/2;
            }
        }
        
        return Math.min(1.0d, dp[query_row][query_glass]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

秋招结束，休息了好长一段时间了。
继续开始给自己充电。