# 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-> 3 -> 4 -> 1 -> 0

Can you enlighten me about the problematic/missing part of this code? Thanks!

• We typically don't debug code here, unfortunately. Commented Mar 23, 2021 at 21:03
• @YuvalFilmus I don't ask anyone to debug my code Sir, I just cannot find any mistake in this code snippet and thought maybe someone can see the logical mistake that I cannot see. Commented Mar 23, 2021 at 21:20
• @Steven sorry, my bad. "profits" was the former name of "rewards". I have just edited my question. 3rd if case stands for the base case: If you go inside 1x1 grid, the return value is the reward of that cell. Commented Mar 23, 2021 at 21:21
• @bbasaran. I still don't understand the logic behind the 3rd if statement. I suspect that's where the error lies. Commented Mar 23, 2021 at 21:24
• @Steven the maximum reward of 1x1 grid is the reward of that cell itself, which is rewards[0][0]. This is the last node of the recursion. Commented Mar 23, 2021 at 21:26

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.