Can you solve this problem using C++?

[Duthomhas]

Alright, I’ll bite.

Gets max gold only

#include <ciso646>
#include <iostream>

constexpr int G_ROWS = 7;
constexpr int G_COLS = 8;
int G[7][8] = 
{
  { 5, 1, 0, 4, 1, 1, 2, 0 },
  { 0, 3, 2, 1, 0, 3, 0, 1 },
  { 4, 3, 0, 6, 5, 0, 1, 0 },
  { 3, 1, 0, 3, 4, 0, 1, 3 },
  { 0, 5, 2, 0, 1, 1, 5, 1 },
  { 2, 1, 6, 1, 6, 0, 2, 1 },
  { 0, 0, 4, 3, 2, 3, 0, 2 }
};

int max_path( int row, int col )
{
  int up = G[ row ][ col ];
  int rt = G[ row ][ col ];
  
  if ((row == 0) and (col == G_COLS-1)) return G[ row ][ col ];
  
  if (row >        0) up += max_path( row-1, col );
  if (col < G_COLS-1) rt += max_path( row, col+1 );
  
  return up > rt ? up : rt;
}

int main()
{
  std::cout << "max gold = " << max_path( G_ROWS-1, 0 ) << "\n";
}

Get max gold and path taken

#include <ciso646>
#include <iostream>
#include <string>

constexpr int G_ROWS = 7;
constexpr int G_COLS = 8;
int G[7][8] = 
{
  { 5, 1, 0, 4, 1, 1, 2, 0 },
  { 0, 3, 2, 1, 0, 3, 0, 1 },
  { 4, 3, 0, 6, 5, 0, 1, 0 },
  { 3, 1, 0, 3, 4, 0, 1, 3 },
  { 0, 5, 2, 0, 1, 1, 5, 1 },
  { 2, 1, 6, 1, 6, 0, 2, 1 },
  { 0, 0, 4, 3, 2, 3, 0, 2 }
};

struct max_path_result
{
  int         gold;
  std::string path;
  max_path_result& operator += ( const max_path_result& that )
  {
    gold += that.gold;
    path += that.path;
    return *this;
  }
};

max_path_result
max_path( int row, int col )
{
  max_path_result up{ G[ row ][ col ], "U" };
  max_path_result rt{ G[ row ][ col ], "R" };
  
  if ((row == 0) and (col == G_COLS-1)) return { G[ row ][ col ], "" };
  
  if (row >        0) up += max_path( row-1, col );
  if (col < G_COLS-1) rt += max_path( row, col+1 );

  return (up.gold > rt.gold) ? up : rt;
}

int main()
{
  auto r = max_path( G_ROWS-1, 0 );
  std::cout << "max gold = " << r.gold << "\n";
  std::cout << "max path = " << r.path << "\n";
}

Simple recursive, non-dynamic, Dijkstra not needed.

[helios]

Is it just me or does your second version return the path in reverse?

[Duthomhas]

Look again. ;-)

[helios]

Ah, I see. It confused me that you both pass the coordinates in y-x order and start the recursion from the start point rather than the end point.
Both calls look identical if you ignore the variable names:
auto r = max_path( G_ROWS-1, 0 );

std::cout << get_best(w - 1, 0) << std::endl;

[lastchance]

@Helios and @Duthomas: thank-you for sharing those recursive codes.

Here's the best space-saving direct version I could come up with. The diagonal front and dependence of steps allows you to overwrite the original matrix. It saves having another array (or an equivalent amount of function pointers in memory for the recursive case). It doesn't store the route though.

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
   const int IMAX = 7, JMAX = 8;
   int A[IMAX][JMAX] = { { 5, 1, 0, 4, 1, 1, 2, 0 },       // Indexing orientation:
                         { 0, 3, 2, 1, 0, 3, 0, 1 },       //      +--------> j         0,0 -------- 0,JMAX-1
                         { 4, 3, 0, 6, 5, 0, 1, 0 },       //      |                     |
                         { 3, 1, 0, 3, 4, 0, 1, 3 },       //      |                     |
                         { 0, 5, 2, 0, 1, 1, 5, 1 },       //      |                     |
                         { 2, 1, 6, 1, 6, 0, 2, 1 },       //     \|/                    |
                         { 0, 0, 4, 3, 2, 3, 0, 2 } };     //      i                 IMAX-1,0

   for ( int d = 1; d <= IMAX + JMAX - 2; d++ )            // d is diagonal (= number of steps here)
   {
      for ( int j = max(0,d+1-IMAX), i = IMAX-1-d+j; j <= min(JMAX-1,d); i++, j++ )
      {
         if      ( j == 0        ) A[i][j] += A[i+1][j];
         else if ( i == IMAX - 1 ) A[i][j] += A[i][j-1];
         else                      A[i][j] += max( A[i][j-1], A[i+1][j] );
      }
   }
   cout << "Most gold is " << A[0][JMAX-1] << '\n';
}

Most gold is 33

[helios]

Ooh! Fun!

#include <iostream>
#include <algorithm>

int map[] = {
	5, 1, 0, 4, 1, 1, 2, 0,
	0, 3, 2, 1, 0, 3, 0, 1,
	4, 3, 0, 6, 5, 0, 1, 0,
	3, 1, 0, 3, 4, 0, 1, 3,
	0, 5, 2, 0, 1, 1, 5, 1,
	2, 1, 6, 1, 6, 0, 2, 1,
	0, 0, 4, 3, 2, 3, 0, 2
};

int main(){
#define f(z) ((y = x), (x += (i & (1 << j)) ? 1 : -z), y)
#define FOR for (int j = 0; j < m; j++)
	int w = 8, h = 7, m = w + h - 2, max = 0;
	for (int i = 0; i < (1 << m); i++){
		int x = 0, y;
		FOR f(1);
		if (x != w - h)
			continue;
		int accum = 0;
		x = (h - 1) * w;
		FOR accum += map[f(w)];
		max = std::max(accum, max);
	}
	std::cout << max << std::endl;
}