LeetCode 799. 香槟塔

Categories:

题目描述
思路分析
1. 解法一：动态规划模拟（推荐）
相似题目

题目描述

✅ 799. 香槟塔

思路分析

解法一：动态规划模拟（推荐）

核心思路：

dp[r][c] 表示流到第 r 行第 c 杯的香槟量。

超过 1 的部分会平均流向下一行的两侧杯子。

只需模拟到目标行即可。

复杂度分析：

时间复杂度：O(r^2)，其中 r 表示目标行编号。

空间复杂度：O(r^2)。

class Solution {
    public double champagneTower(int poured, int queryRow, int queryGlass) {
        double[][] dp = new double[queryRow + 2][queryRow + 2];
        dp[0][0] = poured;

        for (int r = 0; r <= queryRow; r++) {
            for (int c = 0; c <= r; c++) {
                double overflow = Math.max(0.0, dp[r][c] - 1.0);
                if (overflow > 0) {
                    dp[r + 1][c] += overflow / 2.0;
                    dp[r + 1][c + 1] += overflow / 2.0;
                }
            }
        }

        return Math.min(1.0, dp[queryRow][queryGlass]);
    }
}

func champagneTower(poured int, queryRow int, queryGlass int) float64 {
	dp := make([][]float64, queryRow+2)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]float64, queryRow+2)
	}
	dp[0][0] = float64(poured)

	for r := 0; r <= queryRow; r++ {
		for c := 0; c <= r; c++ {
			overflow := dp[r][c] - 1.0
			if overflow > 0 {
				share := overflow / 2.0
				dp[r+1][c] += share
				dp[r+1][c+1] += share
			}
		}
	}

	if dp[queryRow][queryGlass] > 1.0 {
		return 1.0
	}
	return dp[queryRow][queryGlass]
}

相似题目

题目	难度	考察点
62. 不同路径	中等	DP
63. 不同路径 II	中等	DP
688. 骑士在棋盘上的概率	中等	DP
931. 下降路径最小和	中等	DP
1575. 统计所有可行路径	困难	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/28480259