Solution 4 for Scaler Topics Fortnightly Contest - 8

This article is part of the Scaler Topics Fortnightly Contest - 8

Solution Approach

• We use Dynamic Programming to solve this problem.
• Let the states of DP be $dp[idx][waterLeft]$, where idx tells us which index we are currently at and waterLeft tells how much water is left with us to be filled in the rest of $(n - idx)$ buckets.
• At an idx we have two possibilities, either to completely fill that bucket or to skip that bucket.
• Initially we will can $rec(idx = 0, waterLeft = Sum(Bi) )$ to get the answer.

Time Complexity:- $O(N* 100 * N)$

Total Space Complexity:- $O(N * 100 * N)$

C++ Implementation

Java Implementation

Python Implementation