Max Number of Coins, by Zillow

Question today comes from Daily Coding Problem, from Zillow:

This question was asked by Zillow.

You are given a 2-d matrix where each cell represents number of coins in that cell. Assuming we start at matrix[0][0], and can only move right or down, find the maximum number of coins you can collect by the bottom right corner.

For example, in this matrix

0 3 1 1

2 0 0 4

1 5 3 1

The most we can collect is 0 + 2 + 1 + 5 + 3 + 1 = 12 coins.

This is another typical DP problem: it will require O(n)-space to hold the best sums per cell, but the time complexity will be linear, that’s usually the trade-off. The analogy with recursion that I always like to use is to structure the code in terms of Base Case + Construction for DP, instead of Base Case + Induction for Recursion. The solution is in the bottom right corner cell. Works well, code is checked-in on Github (https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem01142019.cs) and down below, thanks, Boris.

public int MaxNumberCoins(int[,] matrix)

{

               if (matrix == null) return 0;

               int R = matrix.GetLength(0);

               int C = matrix.GetLength(1);

               int[,] dp = new int[R, C];

               //Base

               dp[0, 0] = matrix[0, 0];

               for (int c = 1; c < C; c++) dp[0, c] = dp[0, c - 1] + matrix[0, c];

               for (int r = 1; r < R; r++) dp[r, 0] = dp[r - 1, 0] + matrix[r, 0];

               //Construction

               for (int r = 1; r < R; r++)

                              for (int c = 1; c < C; c++)

                                             dp[r, c] = Math.Max(dp[r - 1, c], dp[r, c - 1]) + matrix[r, c];

               return dp[R - 1, C - 1];

}