Here is the implementation for Red Green Towers (Codeforces 478D):
MOD := 1000000007
// Find max height
h := 0
while (h + 1) × (h + 2) / 2 <= r + g
h := h + 1
S := h × (h + 1) / 2
// DP with space optimization (1D array)
dp := array of size S + 1, all set to 0
dp[0] := 1
for i from 1 to h
for j from S down to i
dp[j] := (dp[j] + dp[j - i]) mod MOD
// Sum valid states
answer := 0
for j from 0 to S
if j <= r and S - j <= g then
answer := (answer + dp[j]) mod MOD
return answer
The D array trick works because level adds blocks. Processing from down to prevents counting the same level twice. This is the same reverse-loop pattern from 0/1 knapsack. After all levels, dp[j] holds the number of ways to use exactly red blocks across the full tower. You sum only the entries where both constraints ( and ) are satisfied.
Time complexity: .
Space complexity: where .