Horje
Maximize coins that can be collected by moving on given coordinates

Given an array arr[][] of size N*3 where ith element represents that at time arr[i][0] secs, arr[i][2] coins appear at coordinate arr[i][1]. A player starts on coordinate 0 at time 0sec and can move from one coordinate to any adjacent coordinates in 1 sec and also the player can choose to stay on the same coordinate for the next second. The task is to find how many coins can the player collect.

Note: If a coin appears at time X, it disappears at time X+1.

Examples: 

Input: arr[][3] = {{1, 0, 100}, {3, 3, 10}, {5, 4, 1}}
Output: 101
Explanation: The optimal strategy for players is:  
At T = 0, wait at coordinate 0 to catch coins at T = 1
At T = 1, collect 100 coins
At T = 2, moves to coordinate 1
At T = 3 moves to coordinate 2
At T = 4 moves to coordinate 3
At T = 5, move to coordinate 4 and collect 1 coin that has just appeared.  
Total coins = 100 + 1 = 101

Input: arr[][3] = {{1, 4, 1}, {2, 4, 1}, {3, 4, 1}}
Output: 0

Naive approach: The basic way to solve the problem is as follows:

The basic way to solve this problem is to generate all possible combinations by using recursive approach.

Time Complexity: O(3N)
Auxiliary Space: O(1)

Efficient Approach:  The above approach can be optimized based on the following idea:

Dynamic programming along with hashmap can be used to solve this problem. dp[i][j] = X, represents the maximum coins collected at the time i with coordinate j

it can be observed that the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of each state. This can be done using by store the value of a state and whenever the function is called, return the stored value without computing again.

Follow the steps below to solve the problem:

  • Create a hashmap and map time arr[i][0] and coordinate arr[i][1] to coins arr[i][2]. 
  • Create a recursive function that takes two parameters i representing the current time and j representing the current coordinate.
  • Call the recursive function thrice first for moving backward, second for moving ahead, and third for staying on the same coordinate.
  • Create a 2d array of dp[100001][5] initially filled with -1.
    • If the answer for a particular state is computed then save it in dp[i][j].
    • If the answer for a particular state is already computed then just return dp[i][j].

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Dp table initialized with - 1
int dp[100001][5];
 
// Recursive function to count maximum coins
// player can collect
int recur(int i, int j, vector<vector<int> >& HashMap)
{
    // Base case
    if (i == 100001) {
        return 0;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i][j] != -1)
        return dp[i][j];
 
    int ans = 0;
 
    // Calling recursive function for moving
    // to Right coordinate
    if (j != 4)
        ans = max(ans, recur(i + 1, j + 1, HashMap)
                           + HashMap[i + 1][j + 1]);
 
    // Calling recursive function for
    // staying on same position
    ans = max(ans,
              recur(i + 1, j, HashMap) + HashMap[i + 1][j]);
 
    // Calling recursive function for
    // moving to Left coordinate
    if (j != 0)
        ans = max(ans, recur(i + 1, j - 1, HashMap)
                           + HashMap[i + 1][j - 1]);
 
    // Save and return dp value
    return dp[i][j] = ans;
}
 
// Function to calculate maximum coins
// that player can collect
int findMaximumScore(int arr[][3], int N)
{
    // Filling dp table with -1
    memset(dp, -1, sizeof(dp));
 
    // Initializing hashmap with value 0
    vector<vector<int> > HashMap(100010, vector<int>(6, 0));
 
    // Filling hashmap
    for (int i = 0; i < N; i++) {
 
        // At time arr[i][0] and at coordinate
        // arr[i][1] exactly arr[i][2] coins appear
        HashMap[arr[i][0]][arr[i][1]] = arr[i][2];
    }
 
    return recur(0, 0, HashMap);
}
 
// Driver Code
int main()
{
    // Test Case 1
    int arr[][3]
        = { { 1, 0, 100 }, { 3, 3, 10 }, { 5, 4, 1 } };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << findMaximumScore(arr, N) << endl;
 
    // Test Case 2
    int arr1[][3]
        = { { 1, 4, 1 }, { 2, 4, 1 }, { 3, 4, 1 } };
    int N1 = sizeof(arr1) / sizeof(arr1[0]);
 
    // Function Call
    cout << findMaximumScore(arr1, N1) << endl;
 
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Dp table initialized with - 1
    static int[][] dp = new int[1001][5];
 
    // Recursive function to count maximum coins
    // player can collect
    static int recur(int i, int j, int[][] HashMap)
    {
        // Base case
        if (i == 1001) {
            return 0;
        }
 
        // If answer for current state is already
        // calculated then just return dp[i][j]
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
 
        int ans = 0;
 
        // Calling recursive function for moving
        // to Right coordinate
        if (j != 4) {
            ans = Math.max(ans,
                           recur(i + 1, j + 1, HashMap)
                               + HashMap[i + 1][j + 1]);
        }
 
        // Calling recursive function for
        // staying on same position
        ans = Math.max(ans, recur(i + 1, j, HashMap)
                                + HashMap[i + 1][j]);
 
        // Calling recursive function for
        // moving to Left coordinate
        if (j != 0) {
            ans = Math.max(ans,
                           recur(i + 1, j - 1, HashMap)
                               + HashMap[i + 1][j - 1]);
        }
 
        // Save and return dp value
        return dp[i][j] = ans;
    }
 
    // Function to calculate maximum coins
    // that player can collect
    static int findMaximumScore(int[][] arr, int N)
    {
        // Filling dp table with -1
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
 
        // Initializing hashmap with value 0
        int[][] HashMap = new int[100010][6];
 
        // Filling hashmap
        for (int i = 0; i < N; i++) {
 
            // At time arr[i][0] and at coordinate
            // arr[i][1] exactly arr[i][2] coins appear
            HashMap[arr[i][0]][arr[i][1]] = arr[i][2];
        }
 
        return recur(0, 0, HashMap);
    }
 
    public static void main(String[] args)
    {
        // Test Case 1
        int[][] arr
            = { { 1, 0, 100 }, { 3, 3, 10 }, { 5, 4, 1 } };
        int N = arr.length;
 
        // Function Call
        System.out.println(findMaximumScore(arr, N));
 
        // Test Case 2
        int[][] arr1
            = { { 1, 4, 1 }, { 2, 4, 1 }, { 3, 4, 1 } };
        int N1 = arr1.length;
 
        // Function Call
        System.out.println(findMaximumScore(arr1, N1));
    }
}
 
// This code is contributed by lokesh.

Python3

# Python code to implement the approach
 
# Dp table initialized with - 1
dp=[[-1 for i in range(5)] for j in range(101)]
 
# Recursive function to count maximum coins
# player can collect
def recur(i,j,HashMap):
    # Base case
    if(i==101):
        return 0
     
    # If answer for current state is already
    # calculated then just return dp[i][j]
    if(dp[i][j]!=-1):
        return dp[i][j]
         
    ans=0
     
    # Calling recursive function for moving
    # to Right coordinate
    if(j!=4):
        ans=max(ans,recur(i + 1, j + 1, HashMap) + HashMap[i + 1][j + 1])
     
    # Calling recursive function for
    # staying on same position
    ans = max(ans,recur(i + 1, j, HashMap) + HashMap[i + 1][j])
     
    # Calling recursive function for
    # moving to Left coordinate
    if(j!=0):
        ans = max(ans,recur(i + 1, j - 1, HashMap) + HashMap[i + 1][j - 1])
     
    # Save and return dp value
    dp[i][j]=ans
    return dp[i][j]
     
# Function to calculate maximum coins
# that player can collect
def findMaximumScore(arr,N):
    # Filling dp table with -1
    for i in range(len(dp)):
        for j in range(len(dp[0])):
            dp[i][j]=-1
     
    # Initializing hashmap with value 0
    HashMap=[[0 for i in range(6)] for j in range(100010)]
     
    # Filling hashmap
    for i in range(N):
        # At time arr[i][0] and at coordinate
        # arr[i][1] exactly arr[i][2] coins appear
        HashMap[arr[i][0]][arr[i][1]] = arr[i][2]
     
    return recur(0,0,HashMap)
     
# Driver Code
 
# Test Case 1
arr=[[1, 0, 100],[3, 3, 10],[5, 4, 1]]
N=len(arr)
 
# Function Call
print(findMaximumScore(arr, N))
 
 
# Test Case 2
arr1=[[1, 4, 1],[2, 4, 1],[3, 4, 1]]
N1=len(arr1)
 
# Function Call
print(findMaximumScore(arr1, N1))
 
# This code is contributed by Pushpesh Raj.

C#

// C# code to implement the approach
 
using System;
using System.Linq;
 
public class GFG{
   
      // Dp table initialized with - 1
    static int[,] dp = new int[1001, 5];
 
    // Recursive function to count maximum coins
    // player can collect
    static int Recur(int i, int j, int[,] hashMap)
    {
        // Base case
        if (i == 1001)
        {
            return 0;
        }
 
        // If answer for current state is already
        // calculated then just return dp[i][j]
        if (dp[i, j] != -1)
        {
            return dp[i, j];
        }
 
        int ans = 0;
 
        // Calling recursive function for moving
        // to Right coordinate
        if (j != 4)
        {
            ans = Math.Max(ans,
                           Recur(i + 1, j + 1, hashMap)
                               + hashMap[i + 1, j + 1]);
        }
 
        // Calling recursive function for
        // staying on same position
        ans = Math.Max(ans, Recur(i + 1, j, hashMap)
                                + hashMap[i + 1, j]);
 
        // Calling recursive function for
        // moving to Left coordinate
        if (j != 0)
        {
            ans = Math.Max(ans,
                           Recur(i + 1, j - 1, hashMap)
                               + hashMap[i + 1, j - 1]);
        }
 
        // Save and return dp value
        return dp[i, j] = ans;
    }
 
    // Function to calculate maximum coins
    // that player can collect
    static int FindMaximumScore(int[,] arr, int N)
    {
        // Filling dp table with -1
        for (int i = 0; i < dp.GetLength(0); i++)
        {
            for (int j = 0; j < dp.GetLength(1); j++)
            {
                dp[i, j] = -1;
            }
        }
 
        // Initializing hashmap with value 0
        int[,] hashMap = new int[100010, 6];
 
        // Filling hashmap
        for (int i = 0; i < N; i++)
        {
            // At time arr[i][0] and at coordinate
            // arr[i][1] exactly arr[i][2] coins appear
            hashMap[arr[i, 0], arr[i, 1]] = arr[i, 2];
        }
 
        return Recur(0, 0, hashMap);
    }
 
    static public void Main (){
 
        // Code
          // Test Case 1
        int[, ] arr
            = { { 1, 0, 100 }, { 3, 3, 10 }, { 5, 4, 1 } };
        int N = arr.GetLength(0);
 
        // Function Call
        Console.WriteLine(FindMaximumScore(arr, N));
 
        // Test Case 2
        int[, ] arr1
            = { { 1, 4, 1 }, { 2, 4, 1 }, { 3, 4, 1 } };
        int N1 = arr1.GetLength(0);
 
        // Function Call
        Console.WriteLine(FindMaximumScore(arr1, N1));
    }
}
 
// This code is contributed by lokeshmvs21.

Javascript

  // JS code to implement the approach
 
  // Dp table initialized with - 1
  let dp = new Array(1001)
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(5);
  }
 
  // Recursive function to count maximum coins
  // player can collect
  function recur(i, j, HashMap) {
    // Base case
    if (i == 1001) {
      return 0;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i][j] != -1)
      return dp[i][j];
 
    let ans = 0;
 
    // Calling recursive function for moving
    // to Right coordinate
    if (j != 4)
      ans = Math.max(ans, recur(i + 1, j + 1, HashMap)
        + HashMap[i + 1][j + 1]);
 
    // Calling recursive function for
    // staying on same position
    ans = Math.max(ans,
      recur(i + 1, j, HashMap) + HashMap[i + 1][j]);
 
    // Calling recursive function for
    // moving to Left coordinate
    if (j != 0)
      ans = Math.max(ans, recur(i + 1, j - 1, HashMap)
        + HashMap[i + 1][j - 1]);
 
    // Save and return dp value
    return dp[i][j] = ans;
  }
 
  // Function to calculate maximum coins
  // that player can collect
  function findMaximumScore(arr, N) {
    // Filling dp table with -1
    for (let i = 0; i < dp.length; i++) {
      for (let j = 0; j < dp[i].length; j++) {
        dp[i][j] = -1;
      }
    }
    // Initializing hashmap with value 0
    let HashMap = new Array(100010);
    for (let i = 0; i < HashMap.length; i++) {
      HashMap[i] = new Array(6).fill(0)
    }
 
 
    // Filling hashmap
    for (let i = 0; i < N; i++) {
 
      // At time arr[i][0] and at coordinate
      // arr[i][1] exactly arr[i][2] coins appear
      HashMap[arr[i][0]][arr[i][1]] = arr[i][2];
    }
 
    return recur(0, 0, HashMap);
  }
 
  // Driver Code
 
  // Test Case 1
  let arr
    = [[1, 0, 100], [3, 3, 10], [5, 4, 1]];
  let N = arr.length;
 
  // Function Call
  console.log(findMaximumScore(arr, N) + "<br>");
 
  // Test Case 2
  let arr1
    = [[1, 4, 1], [2, 4, 1], [3, 4, 1]];
  let N1 = arr1.length;
 
  // Function Call
  console.log(findMaximumScore(arr1, N1) + "<br>");
 
 
// This code is contributed by Potta Lokesh

Output

101
0

Time Complexity: O(N * M) where M denotes the maximum amount of time present in array.
Auxiliary Space: O(N * M)

Related Articles:


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Make Array sum even using minimum operations Make Array sum even using minimum operations
Maximum length of sequence formed from cost N Maximum length of sequence formed from cost N
Greedy Best first search algorithm Greedy Best first search algorithm
Hash Table vs Trie Hash Table vs Trie
Regular Expressions to Validate ISBN Code Regular Expressions to Validate ISBN Code

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje