Daily Coding Probleem #15

// 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.

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int coinRecurs(vector<vector<int>> &m, int x, int y, int pathSum)

{

cout << "Pathsum: " << pathSum << endl;

if (x >= m[0].size())

{

return pathSum;

}

if (y >= m.size())

{

return pathSum;

}

return max(coinRecurs(m, x + 1, y, pathSum + m[y][x]), coinRecurs(m, x, y + 1, pathSum + m[y][x]));

}

void printMatrix(vector<vector<int>> m)

{

for (unsigned i = 0; i < m.size(); ++i)

{

for (unsigned j = 0; j < m[i].size(); ++j)

{

cout << m[i][j] << ",";

}

cout << endl;

}

}

vector<vector<int>> buildMatrix()

{

// 0 3 1 1

// 2 0 0 4

// 1 5 3 1

vector<vector<int>> m = vector<vector<int>>();

vector<int> row;

row.push_back(0);

row.push_back(3);

row.push_back(1);

row.push_back(1);

m.push_back(row);

row.clear();

row.push_back(2);

row.push_back(0);

row.push_back(0);

row.push_back(4);

m.push_back(row);

row.clear();

row.push_back(1);

row.push_back(5);

row.push_back(3);

row.push_back(1);

m.push_back(row);

row.clear();

cout << "Matrix is Done!" << endl;

printMatrix(m);

return m;

}

int main()

{

int maxCoins = coinRecurs(buildMatrix(), 0, 0, 0);

cout << "Maximum Coins: " << maxCoins << endl;

return 0;

}