Number of paths, min_cost path via 2D DP created by vetional - https://repl.it/MQuc/3

main.py

# Problem Statement : Given a cost matrix Cost[][] where Cost[i][j] denotes the Cost 
# of visiting cell with coordinates (i,j), find a min-cost path to reach a cell (x,y)
# from cell (0,0) under the condition that you can only travel one step right or one
# step down. (We assume that all costs are positive integers)


def paths(Cost, row, col, dr, dc, memo):

  if row == dr and col == dc:
    return 1
  
  if row > dr or col > dc:
    return 0
  
  key = str(row) + '-' + str(col)
  print key
  if key in memo:
    return memo[key]
  
  print '\t', row, col + 1
  print '\t', row + 1, col
  # go from 0,0 to destination(x,y)
  ways = paths(Cost, row, col + 1, dr, dc, memo) + \
            paths(Cost, row + 1 , col, dr, dc, memo)

  memo[key] = ways
  return ways

def min_cost(Cost, row, col, dr, dc, memo):
  if col == dc and row == dr:
    return 0
  
  if col < 0 or row < 0:
    return max(dr,dc,100)
    
  key = str(row) + '-' + str(col)
  if key in memo:
    # print "found in memo: " + key
    return memo[key]

  # start from end position and retrace path to source    
  mc = Cost[row][col] + min(min_cost(Cost, row, col - 1, dr, dc, memo), \
                            min_cost(Cost, row - 1, col, dr, dc, memo))
  memo[key] = mc
  # print "put in memo :" + key
  return mc

# init cost matrix
rows_count = 15
cols_count = 15
Cost = [[ 0 for x in range(cols_count)] for x in range(rows_count)]

for c in Cost:
  print c

# dr,dc = destination(x,y)
dr = 2
dc = 2
start_row = 0
start_col = 0
memo = {}

print "start: ", start_row, start_col
print "destination: ", dr, dc

print "Min Cost: " +  str(min_cost(Cost, dr, dc, start_row, start_col, memo))
pmemo = {}
print "Paths: " +  str(paths(Cost,  start_row, start_col, dr, dc, pmemo))