Consider a n x m board, where there is at most one coin per cell. A robot, locat

Question

Consider a n x m board, where there is at most one coin per cell. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location. When the robot visits a cell with a coin, it picks up that coin. Give an optimal dynamic programming algorithm to find the maximum number of coins the robot can collect. In your algorithmic description, you must include the recurrence equation for your algorithm along with a description of the underlying subproblems that need to solved.

Explanation / Answer

#include <iostream>
using namespace std;

int numberOfCoins(int m, int n)
{
   // Create a 2D table to store results of subproblems
   int count[m][n];

   // Count the coin to reach any cell in first column is 1
   for (int i = 0; i < m; i++)
       count[i][0] = 1;

   for (int j = 0; j < n; j++)
       count[0][j] = 1;

   for (int i = 1; i < m; i++)
   {
       for (int j = 1; j < n; j++)

          
           count[i][j] = count[i-1][j] + count[i][j-1]; //+ count[i-1][j-1];

   }
   return count[m-1][n-1];
}

int main()
{
   cout << numberOfCoins(3, 3);
   return 0;
}

OUPTPUT is : 6

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.