Question

1. Given a matrix ? (i.e., a 2D table) of positive integers of size ? × ?. A robot starts at the top- left position ?[?, ?] and must reach the bottom-right position ?[?, ?]. From a position ?[?, ?], the robot can only go either right to ?[?, ? + ?] or down to ?[? + ?, ?]. Let us define the cost of a path the total values of integers in it. Find the least-cost path for the robot to reach to bottom- right. How about the path with the maximum cost? Prove python source code, time complexity, and pseudocode.

   Input: Matrix ? and its sizes ? and ?
   Output: A sequence of pairs of index (?, ?)’s for the least-cost path from ?[1,1] to ?[?, ?]

Answer 1

//psuedo code
minPath(matrix,n,m):
    if(n<0 or m<0):
        return maxvalue
    else if(n==0 or m==0):
        return matrix[n][m]
    else
       return matrix[n][m]+min(minCost(minCost(cost, m-1, n),minCost(cost, m, n-1))

//Time Complexity will be
O(n+m)
as we just doing one pass here 

//max path
if we want to find max cost path here instead of taking min of bottom and right we shall take max of bottom and right





//python code
import sys



def minCost(cost, m, n):
   if (n < 0 or m < 0):
      return sys.maxsize
   elif (m == 0 and n == 0):
      return cost[m][n]
   else:
      return cost[m][n] + min(minCost(cost, m-1, n),
                        minCost(cost, m, n-1))

 


R = int(input("Enter the number of rows:"))
C = int(input("Enter the number of columns:"))
cost = []
print("Enter the entries rowwise:")


for i in range(R):
    a = []
    for j in range(C):
        a.append(int(input()))
    cost.append(a)

for i in range(R):
    for j in range(C):
        print(cost[i][j], end=" ")
    print()

print(minCost(cost, R-1 ,C-1))