Write an efficient algorithm for the following problem, briefly describe why it is a correct algorithm, and analyze the time complexity. If you cannot find any polynomial-time algorithm, then give a backtracking algorithm.

• Problem: RobotWalk
• Input: An array A[1...n,1...n] of positive integers. A robot that starts at position A[0,0] and wants to reach A[n,n]. At each step, the robot can only move on step either upward or rightward. For example, if the current position is (i,j), then the next possible positions are (i,j+1), (i+1,j+1), or (i+1,j). The cost of a path is the sum of the entries that the robot visits.
• Example: Input: A =

  50	20	30 (robot ends at A[n,n])
  10	10	10
  10 (robot Starts at A[0,0])	40	40

  Output: 50 (because of the path 10 -> 10 -> 30

• Output: The length of the shortest path that the robot can take.