[LeetCode]Champagne Tower

这道题我们老老实实地从上到下计算即可，用dp[i][j]表示第i行第j个被子剩下的体积，j <= i，那么我们有递推公式：

• dp[i][j] = max((dp[i - 1][j] - 1) / 2, 0), if i == 0
• dp[i][j] = max((dp[i - 1][j - 1] - 1) / 2, 0), if i == j
• dp[i][j] = max((dp[i - 1][j] + dp[i - 1][j - 1] - 1) / 2, 0), if 0 < i < j

因为最多有99行和99列，我们遍历完所有的i和j即可。假设输入有n行，那么时间复杂度和空间复杂度为O(n^2)，这道题行数最大99，所以也可以说是O(1)。代码如下：