Write a function that takes a pair of indices for a 2D array and prints out the number at the provided indices where each number is the sum of the value to the left and above itself. the first row and the first column are filled with 1s. So the value at (row, col) is (row-1, col) + (row,col-1) :(0,0) is 1, (1,1) is 2, (2,1) is 3, (5,3) is 56 and so on.

Currently, I have a O(m*n) solution, but I need to optimize this further. this is my O(m*n) solution using dynamic programming:

from functools import lru_cache

def uniquePaths(m: int, n: int): @lru_cache(maxsize=None) def dp(row, col): print(".") if row == 0 or col == 0: return 1

return dp(row - 1, col) + dp(row, col - 1)

return dp(m, n)

row = int(input('row? ')) col = int(input('col? '))

print(uniquePaths(row, col))