Travelling Salesman Problem with Memoization I coded a solution for the famous Travelling Salesman Problem but my code does not work properly, although it seems okay.

In a grid of size m x n, you are allowed to move only down/right, and
you need to go from the top-left corner to the bottom-right corner.
Each sell has a reward value. How much is the maximum reward you can
collect?

def travellingSalesman(m, n, rewards, memo={}):

  if m == 0 or n == 0:    return 0
  if (m, n) in memo:      return memo[(m, n)]
  if (n, m) in memo:      return memo[(n, m)]

  # Base case
  if m == 1 and n == 1:   return rewards[0][0]
  
  # maximum rewarding one of the grids m-1 x n - m x n-1 plus reward of the current cell
  memo[(m, n)] = max(travellingSalesman(m-1, n, rewards, memo), travellingSalesman(m, n-1, rewards, memo)) + rewards[m-1][n-1]

  return memo[(m, n)]

if __name__ == '__main__':
  print(travellingSalesman(m=3, n=3, rewards=[[0,4,2], 
                                              [3,2,0], 
                                              [4,1,0]]))

The function below returns 6, but it should return 8 with the path: 0-&gt; 3 -&gt; 4 -&gt; 1 -&gt; 0
Can you enlighten me about the problematic/missing part of this code? Thanks!
In the 3rd if statement your code assumes that the optimal solution when starting from coordinates $(m, n)$ is equal to the optimal solution when starting from coordinates $(n, m)$. This is clearly false in general.