- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a 2D matrix where each cell stores some coins. If we start from [0,0], and can only move right or down, we have to find the maximum number of coins we can collect by the bottom right corner.

So, if the input is like

1 | 4 | 2 | 2 |

0 | 0 | 0 | 5 |

then the output will be 14, as we take the path: [1, 4, 2, 2, 5]

To solve this, we will follow these steps−

for r in range 1 to row count of A, do

A[r, 0] := A[r, 0] + A[r-1, 0]

for c in range 1 to column count of A, do

A[0, c] := A[0, c] + A[0, c-1]

for r in range 1 to size of A, do

for c in range 1 to size of A[0], do

A[r, c] = A[r, c] + maximum of (A[r-1, c] and A[r, c-1]

return value of bottom right corner of A

Let us see the following implementation to get better understanding−

class Solution: def solve(self, A): for r in range(1, len(A)): A[r][0] += A[r-1][0] for c in range(1, len(A[0])): A[0][c] += A[0][c-1] for r in range(1, len(A)): for c in range(1, len(A[0])): A[r][c] += max(A[r-1][c], A[r][c-1]) return A[-1][-1] ob = Solution() matrix = [ [1, 4, 2, 2], [6, 0, 0, 5] ] print(ob.solve(matrix))

matrix = [ [1, 4, 2, 2], [6, 0, 0, 5] ]

14

- Related Questions & Answers
- Program to find maximum number of coins we can get using Python
- Program to find maximum amount of coin we can collect from a given matrix in Python
- Program to count number of ways we can distribute coins to workers in Python
- Program to find number of distinct coin sums we can make with coins and quantities in Python?
- Problem to Find Out the Maximum Number of Coins that Can be Collected in Python
- Program to find number of coins we can pick from topleft to bottom-right cell and return in Python
- Program to find maximum number of boxes we can fit inside another boxes in python
- Program to find number of combinations of coins to reach target in Python
- Program to find number of coins needed to make the changes with given set of coins in Python
- Program to find maximum number of courses we can take based on interval time in Python?
- Program to find number of coins needed to make the changes in Python
- Program to find number of ways we can decode a message in Python
- Program to find number of ways we can split a palindrome in python
- Program to find maximum how many water bottles we can drink in Python
- C/C++ Program for Greedy Algorithm to find Minimum number of Coins

Advertisements