leetCode779香槟塔

779 香槟塔

注意点： 下标都是从0开始的。

第一行： row=0。将所有的酒都倒入第一个杯子；

第二行： row=1。用第一行的酒-1，然后分别倒入第二行的两个杯子；

第三行： row=2。第二行有两个杯子，把第一个杯子的酒分别倒入第三行的0、1两个杯子中，第二个杯子分别倒入第三行的1、2两个杯子中。

代码：

public double champagneTower(int poured, int query_row, int query_glass) {
  // 全部倒入第一个杯子中
  double[] row = {poured};
  // 从第二行开始
  for (int i = 1; i <= query_row; i++) {
    // 新建当前行的数组,每一行的杯子数量都是行数+1
    double[] nextRow = new double[1+i];
    // 遍历上一行的杯子
    for (int j = 0; j < i; j ++) {
      double v = row[j];
      if (v > 1){
        nextRow[j] += (v - 1) / 2;
        nextRow[j+1] += (v - 1) / 2;
      }
    }
    row = nextRow;
  }
  // 由于多的酒会洒到地上，杯子里面最多是满的。
  return Math.min(1, row[query_glass]);
}