# Recursion

def min_cost(cost,m,n):

if (n<0 or m<0):

return sys.maxsize

if (m==0 and n==0):

return cost[m][n]

else:

return cost[m][n]+min(min_cost(cost,m-1,n-1),

min_cost(cost,m-1,n),

min_cost(cost,m,n-1))

#Dynamic Programming

def min_cost_dp(cost_mat,m,n):

dp=[[0 for i in range(m+1)]

for j in range(n+1)]

dp[0][0]=cost_mat[0][0]

for i in range(1,m+1):

dp[i][0]=dp[i-1][0]+cost_mat[i][0]

for j in range(1,n+1):

dp[0][j]=dp[0][j-1]+cost_mat[0][j]

for i in range(1,m+1):

for j in range(1,n+1):

dp[i][j]=cost_mat[i][j]+min(dp[i-1][j-1],

dp[i-1][j],

dp[i][j-1])

return dp[m][n]