**Problem Statement:Coin Collection Dynamic Programming**

Given a rectangular grid where each cell contains some coins. You are at the first row and you want to go to the last row with the objective of collecting the maximum number of coins on the way.

The allowed moves are down, left diagonal down and right diagonal down. And you are not allowed to step out of rectangle. So what is maximum number or coins that you can accumulate?

**NOTE-** You can start from any point on first row and end on any point on last row. Each entry in grid is positive i.e. greater than 0.

**Solution:**

Since we can start from any point on first row and end on any point on last row and collect as many coins as possible, we may get the feeling that we have to apply either greedy or dynamic programming strategy i.e. either see local maximum or global maximum. Here we can apply complete search but it would be too exhaustive as there would be a large number of overlapping subproblems.

In greedy, our strategy would be start from the point on first row with the maximum coins and then go to point on the next row out of the three points(i.e. **Down** or **left diagonal down** or **right diagonal down**). Thus continue this till we reach we reach the last row.

But there is a problem in using this strategy as we will see in this example.

Now lets see the implementation using Dynamic programming. Before that let us figure out the sub problem in this case.

**Sub problem**

Suppose we are given a matrix S with **r** rows and **c** columns and each entry is some positive integer. Let **S****i,j** be element in **i****th** row and **j****th** column.

So let’s proceed in the following manner-

- If
**S****i,j**is the first element in the ith row, then either it could have come from**S****i-1,j**or**S****i-1,j+1****.** - If
**S****i,j**is the last element in the ith row, then either it could have come from**S****i-1,j**or**S****i-1,j-1****.** - Else
**S****i,j**could have come from either**S****i-1,j**or**S****i-1,j+1**or**S****i-1,j+1****.**

**Dynamic Programming**

Let us create a 2d matrix **dp** of dimension r*c i.e. r rows and c columns.

First we will initialize the first row of **dp **with the first row of **S** i.e. **dp[0][i]=S[0] [i]** ∀ 0≤i≤c-1**. **Then for the rest of the rows we will solve according to the sub problem.

Thus, we will do these-

**dp[i][j]=max(dp[i-1][j] , dp[i-1][j+1])+S[i][j]**for first element in ith row.**dp[i][j]=max(dp[i-1][j] , dp[i-1][j-1])+S[i][j]**for last element in ith row.**dp[i][j]=max(dp[i-1][j] , dp[i-1][j-1] , dp[i-1][j+1])+S[i][j]**for the rest of the elements.

After that we will find the maximum entry from the last row of **dp**, that is our answer.

Let’s see an example.

**Code**

Implemented in C++

#include <bits/stdc++.h> using namespace std; int s[102][102],dp[102][102]; // 2d matrix for s and dp int main(){ int h,w; // h is no. of rows and w is no. of columns cin>>h>>w; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ cin>>s[i][j]; } } for(int i=0;i<w;i++) dp[0][i]=s[0][i]; // initialising first row for(int i=1;i<h;i++){ for(int j=0;j<w;j++){ if(j==0){ dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+s[i][j]; // case where element is first in row } else if(j==w-1){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+s[i][j]; // case where element is last in row } else{ dp[i][j]=max(dp[i-1][j],max(dp[i-1][j-1],dp[i-1][j+1]))+s[i][j]; // all the rest elements } } } /*for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ cout<<dp[i][j]<<" "; } cout<<"\n"; }*/ int maxx=-1; for(int i=0;i<w;i++){ if(maxx<dp[h-1][i]) // finding maximum among last row of dp maxx=dp[h-1][i]; } cout<<maxx<<"\n"; return 0; }

**Complexity**

Both time and space complexities are **O(|no. of rows|*********|no. of columns|).**

Coin Collection Dynamic Programming Article is Published by Arnab Ghosh.

If you want to be a content writer with Gohired.in, please write at career@gohired.in or at admin@gohired.in.

## Leave a Reply