Solution 4 for Scaler Topics Fortnightly Contest - 7

This article is part of the Scaler Topics Fortnightly Contest - 7.

Solution Approach

• Let's build the following dp transitions: dp[i][0] : minimum cost required to build first i bridges, when (i+1) bridge is not built. dp[i][1] : minimum cost required to build first i bridges, when (i+1) bridge is already built.
• Base Cases: dp[0][0] : A[0], because no bridge lies to the left of 0th bridge, and bridge at index 1 is not built. dp[0][1] : B[0], because no bridge lies to the left of 0th bridge, and bridge at index 1 is already built.
• Then final answer will be: dp[n-1][0].

Time Complexity: O(N). Space Complexity: O(N).

C++ Implementation

Java Implementation

Python Implementation