Solution 3 for Scaler Topics Fortnightly Contest - 3

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

Solution Approach

• We can use dynamic programming to calculate all possible states and get our answer.
• Our states would be dp[row][col][type], which would denote the maximum possible number of candies one can collect when reaching cell(row, col).
• The matrix (whether it is matrix C or D) of the corresponding cell would be denoted using "type" state.
• If type is equals to 0, then we are in matrix C and if type is equals to 1, then we are in matrix D.
• Our final answer would be maximum of dp[A - 1][B - 1][0] and dp[A - 1][B - 1][1].

C++ Implementation

Java Implementation

Python Implementation