• 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

TicTacToe Game As Asked in Flipkart

Circular Linked List

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Level order traversal in Spiral form

Serialise Deserialise N-ary Tree

Maximum sum contiguous subarray of an Array

The greedy coins game Dynamic Programming

Printing Longest Common Subsequence

Doubly linked list

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

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

Find Nearest Minimum number in left side in O(n)

Client Server C program

SAP Hiring Off-Campus General Aptitude

Apriori algorithm C Code Data Mining

Walmart Labs Interview Experience

Daughter’s Age VeryGood Puzzle

C++ OOPs Part1

Python List

VMWare Openings

Fibonacci Hashing & Fastest Hashtable

Flipkart SDET Interview Experience

Find the element that appears once others appears thrice

Templates in C++

Find the smallest window in a string containing all characters of another string

Find loop in Singly linked list

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

Max Sum in circularly situated Values

DFS (Depth First Search)

Copyright © 2025 · Genesis Framework · WordPress · Log in