Find Maximum coins to reach bottom right corner

You are given a 2-d matrix where each cell represents the 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.

Example:

Input:  coins= {{0,3,1,1},{2,0,0,4},{1,5,3,1}}
Output: 12

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int maxCoins(vector<vector<int>> coins)
{
    int n = coins.size();

    int m = coins[0].size();

    int dp[n + 1][m + 1];

    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {

            //if we are in the first row
            if (i == 0)
            {
                dp[i][j] = dp[i][j] + coins[i][j];
            }

            //if we are in the first column
            else if (j == 0)
            {
                dp[i][j] = dp[i][j] + coins[i][j];
            }

            //else we take max of both
            else
            {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) 
       + coins[i][j];
            }
        }
    }
    return dp[n - 1][m - 1];
}
int main()
{
    vector<vector<int>> coins = {{0, 3, 1, 1},
                                 {2, 0, 0, 4},
                                 {1, 5, 3, 1}};

    cout << maxCoins(coins);

    return 0;
}