Daily LeetCode – day0114 0799. Champagne Tower

// 0799. Champagne Tower
class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] glasses = new double[query_row + 1][query_row + 1];
        glasses[0][0] = poured;
        for (int i = 1; i <= query_row; ++i) {
            glasses[i][0] = Math.max((glasses[i - 1][0] - 1) / 2, 0.0);
            for (int j = 1; j <= i; ++j) {
                glasses[i][j] = Math.max((glasses[i - 1][j - 1] - 1) / 2, 0.0) + Math.max((glasses[i - 1][j] - 1) / 2, 0.0);
            }
        }
        if (glasses[query_row][query_glass] > 1) {
            return 1.0;
        }
        return glasses[query_row][query_glass];
    }
}
学习笔记:
这是一道有趣的动态规划题目,香槟塔往下流的时候会少1,然后平分给下面两个。
我们需要使用逆向思维,下面那一杯接到的酒就上上面两个流下来的加起来。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

Daily LeetCode – day0114 0799. Champagne Tower》有2条回应

  1. Finger说:

    你的代码就像诗一样

  2. Hummin说:

    你就是算法之王

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注