Introduction

This is the classic champagne-tower style dynamic programming problem. Each cup can hold at most one unit of water, and any overflow splits equally into the two cups directly below, so the amount in cup (row, col) is determined entirely by the overflow arriving from the cups above it.

Model the Overflow, Not Just the Final Fill

The cleanest way to solve the problem is to simulate how much water reaches each cup, row by row. A cup keeps up to one unit and sends the excess downward.

If a cup contains x units, then:

• it retains min(1, x)
• it overflows max(0, x - 1)
• half of that overflow goes left-down
• half goes right-down

That immediately suggests a dynamic programming table.

A Direct Dynamic Programming Solution

In zero-based indexing, let dp[r][c] mean the total water that reaches cup c in row r before capping it at one unit.

1def water_in_cup(poured, target_row, target_col):
2    dp = [[0.0] * (r + 1) for r in range(target_row + 2)]
3    dp[0][0] = float(poured)
4
5    for r in range(target_row + 1):
6        for c in range(r + 1):
7            overflow = max(0.0, dp[r][c] - 1.0)
8            if overflow > 0:
9                dp[r + 1][c] += overflow / 2.0
10                dp[r + 1][c + 1] += overflow / 2.0
11
12    return min(1.0, dp[target_row][target_col])
13
14
15print(water_in_cup(5, 2, 1))

This returns the final amount in the requested cup, capped at the cup capacity of one unit.

Walk Through a Small Example

Suppose you pour 5 units into the top cup.

Row 0:

• cup (0, 0) receives 5
• it keeps 1
• overflow is 4
• each cup below receives 2

Row 1:

• cup (1, 0) receives 2, keeps 1, overflows 1
• cup (1, 1) receives 2, keeps 1, overflows 1
• each overflow contributes 0.5 to each child below

Row 2 becomes:

• cup (2, 0) gets 0.5
• cup (2, 1) gets 1.0
• cup (2, 2) gets 0.5

So the water in cup (2, 1) is exactly 1.0.

That example shows why the recurrence is local and easy to compute iteratively.

Why Dynamic Programming Fits Naturally

The amount in any cup depends only on the two parents above it. There is no need for recursion with repeated recomputation or for simulating every droplet individually.

The state transition is:

overflow = max(0, dp[r][c] - 1)
dp[r+1][c]   += overflow / 2
dp[r+1][c+1] += overflow / 2

That is exactly the kind of overlapping structure dynamic programming handles well.

Space Optimization Is Possible

If you only need one target row, you can optimize space and keep only the current row and next row. But for clarity, the 2D table is usually better, especially in interviews or educational explanations.

A row-by-row version still follows the same logic:

1def water_in_cup_optimized(poured, target_row, target_col):
2    row = [float(poured)]
3
4    for _ in range(target_row):
5        next_row = [0.0] * (len(row) + 1)
6        for i, value in enumerate(row):
7            overflow = max(0.0, value - 1.0)
8            if overflow > 0:
9                next_row[i] += overflow / 2.0
10                next_row[i + 1] += overflow / 2.0
11        row = next_row
12
13    return min(1.0, row[target_col])

This reduces memory usage from a triangle of rows to just one working row.

Common Pitfalls

• Returning the raw amount that reaches the cup instead of capping it at 1 gives the wrong final water content for a single cup.
• Using one-based and zero-based indexing inconsistently is a common source of off-by-one errors.
• Simulating water drop by drop is unnecessarily slow when a direct overflow recurrence solves the problem cleanly.
• Forgetting that overflow splits equally between the two child cups changes the recurrence completely.
• Building the table deeper than necessary wastes work when the question asks only for one target row.

Summary

• Treat the problem as a dynamic programming overflow simulation.
• Each cup keeps up to one unit and splits any excess equally into the two cups below.
• A simple row-by-row DP table gives the answer efficiently.
• Cap the final value at 1 because a cup cannot hold more than its capacity.
• Use the optimized one-row version if you only care about a specific target row.