using c language to compile belows Maximum Number of Golden

using c language to compile belows.

Maximum Number of Golden Coins

A table is composed of m x n cells. Each cell contains a number of golden coins. An example is as follows:

You start at the upper-left cell and want to reach the bottom-right cell. At each step, you can go either down or right one cell. Write a program that uses dynamic programming to find the maximum number of golden coins you can collect.

The output from your program should display the cache table where the maximum number of golden coins collected on a path from the top-left cell to cell (r, c) is stored in cell (r, c). Also output a message indicating the maximum number of coins on a path from the top-left cell to the right-bottom cell. Sample output for the above grid is as follows (Note: you do not have to show borders around the cells, and the leading zeros shown in the first row are just an artifact needed for proper column alignment in this simplified markdown format. Your output shall notcontain these leading zeros and yet still be right-aligned.):

The program should read input from an input file. The file contains the description of an unspecified number of tables. The data for each table starts with two numbers representing the number of rows and columns in the table. This is followed by the number of coins on each row. For example, the top table is represented as follows:

Another sample input file with three tables is as follows:

For each input table, display the corresponding cache table following by a message indicating the maximum number of golden coins that we can collect.

Solution

/* Dynamic Programming implementation of MCP problem */
#include<bits/stdc++.h>
#include<limits.h>
#define R 100
#define C 100
using namespace std;
int max(int x, int y, int z);
int tc[R][C];
int minCost(int cost[R][C], int m, int n)
{
int i, j;

// Instead of following line, we can use int tc[m+1][n+1] or
// dynamically allocate memoery to save space. The following line is
// used to keep te program simple and make it working on all compilers.
//int tc[R][C];

tc[0][0] = cost[0][0];

/* Initialize first column of total cost(tc) array */
for (i = 1; i <= m; i++)
tc[i][0] = tc[i-1][0] + cost[i][0];

/* Initialize first row of tc array */
for (j = 1; j <= n; j++)
tc[0][j] = tc[0][j-1] + cost[0][j];

/* Construct rest of the tc array */
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
tc[i][j] = max(tc[i-1][j-1],
tc[i-1][j],
tc[i][j-1]) + cost[i][j];

return tc[m][n];
}

/* A utility function that returns minimum of 3 integers */
int max(int x, int y, int z)
{
if (x > y)
return (x > z)? x : z;
else
return (y > z)? y : z;
}

/* Driver program to test above functions */
int main()
{

ifstream f(\"input.txt\");

int m,n;

while (!f.eof())
{

f>>m;
f>>n;

  
  
int cost[R][C];
for (int y = 0; y < m; y++) {
for (int x = 0; x < n ; x++) {
f>>cost[x][y];
}
}
printf(\" %d\ \", minCost(cost, m, n));

for (int y = 0; y <m; y++) {
for (int x = 0; x <n ; x++) {
cout<<tc[x][y]<< \" \";
}
cout<<endl;
}

}
return 0;
}

=========================================

output:

20
5 8 17
12 14 19
14 17 20
18
7 9 13
8 14 15
40
7 10 14 19 22
9 11 18 27 29
18 20 24 30 31
19 22 27 34 40
40
7 10 14 19 22
9 11 18 27 29
18 20 24 30 31
19 22 27 34 40