• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Coin Collection Dynamic Programming

February 4, 2018 by Dhaval Dave

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.

Greedy failure 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 Si,j be element in ith row and jth column.

So let’s proceed in the following manner-

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

Sub problem

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.

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

Similar Articles

Filed Under: Algorithm, Interview Questions Tagged With: 2d matrix, Dynamic Programming

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Closed Parentheses checker

Generate next palindrome number

The greedy coins game Dynamic Programming

Print all nodes that are at distance k from a leaf node

Get K Max and Delete K Max in stream of incoming integers

Calculate price of parking from parking start end time prices

Find Percentage of Words matching in Two Strings

Find position of the only set bit

Check if an array has duplicate numbers in O(n) time and O(1) space

Print vertical sum of all the axis in the given binary tree

Find min element in Sorted Rotated Array (With Duplicates)

Implement a generic binary search algorithm for Integer Double String etc

Add Sub Multiply very large number stored as string

Daughter’s Age VeryGood Puzzle

Find if two rectangles overlap

FizzBuzz Solution C C++

C Program for TAIL command of UNIX

simple sql injection

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Microsoft BING Interview Experience

C++ OOPs Part2

Leetcode: Merge Intervals

Word Break Problem

Cisco Hiring Event 21st – 22nd Feb 2015

Number of Islands BFS/DFS

Facebook Interview Question : Interleave List

Code Chef PRGIFT Solution

Skiing on Mountains Matrix

Maximum size of square sub matrix with all 1’s in a binary matrix

Copyright © 2026 · Genesis Framework · WordPress · Log in