Max Path Sum

Given a grid, find the largest sum of all possible paths only moving down or to the right.

Problem from structy.net

Write a function, maxPathSum, that takes in a grid as an argument. The function should return the maximum sum possible by traveling a path from the top-left corner to the bottom-right corner. You may only travel through the grid by moving down or right.

You can assume that all numbers are non-negative.

Not having a formal computer science background, I always assumed these problems were trivial once you learned the "trick," and I believe I've learned the "trick" to these. This problem took me around 5 minutes to solve. My first implementation passed all test correctly and in an appropriate amount of time.

This was always always my worry when I was interviewing before: this was just some club I wasn't a part of. I hope the other concepts, (grid, tree, graph, etc.) aren't like this, but I have a feeling it will be the same...

I've spent a lot of time trying to understand what "good" code meant and how to bring it about. Kvelin Henney and Douglas Crockford are the two that stick out, but I've watched many more people that were less talented in their oration or presentation, but had a lot of good things to say. I've tried to take the best from each and combine them into some sort of "best practices" for myself. To understand why they prefer a certain style or method, how they discover these patterns, and to "battle" those ideas against the others. These are my tools. This was always coding to me: to bring about something like the platonic form of the thing I was building. To have each piece simple, easy, and pure.

Anyways, they always say they care more about how you think and such rather than actually solving the problem, but that's never been true from what I've experienced. Maybe it's just impossible to express that idealism and dedication in a typical coding interview... Well, soon I'll have these algorithms down anyways...

My Solution

function stringifyCoords(x, y) {
  return `${x},${y}`;
}
 
const maxPathSum = (grid, row = 0, col = 0, cache = {}) => {
  const isRowOutOfBounds = row > grid.length - 1;
  const isColOutOfBounds = col > grid[0].length - 1;
  
  if(cache[stringifyCoords(row, col)]) {
    return cache[stringifyCoords(row, col)];
  } else if(isRowOutOfBounds || isColOutOfBounds) {
    return 0;
  } else {
    cache[stringifyCoords(row, col)] = grid[row][col] + Math.max(
      maxPathSum(grid, row + 1, col, cache),
      maxPathSum(grid, row, col + 1, cache)
    );
    
    return cache[stringifyCoords(row, col)];
  }
};