Finding a path travel cost closest to a given value

Question

I have been stuck on a problem recently. I have to find the cost of a path from the top left corner to the bottom right corner of a multidimensional array of integers. This path's cost has to be the greatest cost that does not go over a certain provided value.

The cost of a path is defined as the sum of the values of the array indexes that this path travels through. The start of each path is always the top left corner, and the end of each path is always the bottom right corner. Also, you can only travel to the right or toward the bottom.

Let's say this is the multidimensional array that I am to use for this problem, and the provided value is 12.

+---+---+---+
| 0 | 2 | 5 |
+---+---+---+
| 1 | 1 | 3 |
+---+---+---+
| 2 | 1 | 1 |
+---+---+---+

This is the correct path that I am supposed to find. The cost for this path is 11, it is the highest cost of any path that is below or equal to the given value.

+---+---+---+
| X | X | X |
+---+---+---+
| 1 | 1 | X |
+---+---+---+
| 2 | 1 | X |
+---+---+---+

I have attempted to solve this problem in Python, but I cannot see where I am going wrong. Here is a segment of my code below.

def answer (food, grid):

    # Grid is N*N in size
    n = len(grid)

    # Memoize a given function
    def memoize (f):
        memo = {}
        def helper (r, c, k):
            i = c + (r * n)
            if i not in memo:
                memo[i] = f(r, c, k)
            return memo[i]
        return helper

    # Get cost function
    def get_cost (r, c, k):

        if r >= n or c >= n:
            return -1
        if k < grid[r][c]:
            return -1
        if r == n - 1 and c == n - 1:
            return grid[r][c]

        down = get_cost(r + 1, c, k - grid[r][c])
        right = get_cost(r, c + 1, k - grid[r][c])

        if down < 0 and right < 0:
            return -1

        return grid[r][c] + max(down, right)

    # Memoize the get cost function
    get_cost = memoize(get_cost)

    return get_cost(0, 0, food)

print answer (12, [[0, 2, 5], [1, 1, 3], [2, 1, 1]])

I am always getting the answer of 16, where I should be getting the answer of 11. Can anyone help me with this?

Edit:

I changed my memoize code to include the given food value in the index. And I have gotten the correct answer. However, there are still other cases where it does not work. (I am not provided the input in these cases so I cannot see where it went wrong).

Here is my updated code.

# Memoize a given function
    def memoize (f):
        memo = {}
        def helper (r, c, k):
            i = (k * food) + (c + (r * n))
            if i not in memo:
                memo[i] = f(r, c, k)
            return memo[i]
        return helper

Answer 1

You can update your memoize function to something like this:

def memoize (f):
    memo = {}
    def helper(*args):
        if args not in memo:
            memo[args] = f(*args)
        return memo[args]
    return helper

---

grid = [[0,2,5],[1,1,3],[2,1,1]]
answer(12, grid)
# 11

---

As long as your arguments are hashable, you can use *args as a argument to your function and args as the key to the memoization cache. This is the same as using a tuple of the arguments as the key.

def fn(*args):
    print(args)

fn(1,2,3)
(1, 2, 3)

The original memoization cache keys made up by i = c + (r * n) excluded taking into account the k and also allowed for possible collisions for different c and r combinations.