title: Finding a path travel cost closest to a given value
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>Let's say this is the multidimensional array that I am to use for this problem, and the provided value is 12.</p>
  
  <pre><code>+---+---+---+
  | 0 | 2 | 5 |
  +---+---+---+
  | 1 | 1 | 3 |
  +---+---+---+
  | 2 | 1 | 1 |
  +---+---+---+
  </code></pre>
  
  <p>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.</p>
  
  <pre><code>+---+---+---+
  | X | X | X |
  +---+---+---+
  | 1 | 1 | X |
  +---+---+---+
  | 2 | 1 | X |
  +---+---+---+
  </code></pre>
  
  <p>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.</p>
  
  <pre><code>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 &gt;= n or c &gt;= n:
              return -1
          if k &lt; 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 &lt; 0 and right &lt; 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]])
  </code></pre>
  
  <p>I am always getting the answer of 16, where I should be getting the answer of 11. Can anyone help me with this?</p>
  
  <p>Edit:</p>
  
  <p>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).</p>
  
  <p>Here is my updated code.</p>
  
  <pre><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
  </code></pre>