Code to be written in python:

Correct answer will automatically be awarded the brainliest.

One of the senior wizards Yee Sian was trapped in a maze during a mission. The maze has n * m cells, labelled from (0, 0) to (n-1, m-1). Starting at cell (0, 0), each time Yee Sian can only take one step, either to the right or down. We wish to find out the number of possible paths to the destination (n - 1, m - 1). A sample path is shown in the figure below.

Having learnt the technique of speeding up the pascal function through memoization, you decide to apply it here. If Yee Sian can walk out by himself (number of paths > 0), tell him how many ways there are. Otherwise, report to Grandwizard and send a rescue team.

Write a function num_of_paths that takes in two integers representing the number of rows (n) and columns (m) in a maze and returns an integer value of number of paths from cell (0, 0) to cell (n - 1, m - 1). The table and skeleton code are given to you. Your table is essentially a dictionary that stores (i, j): val pairs which indicate the number of paths from cell (0, 0) to cell (i, j).

Note: You may assume that all inputs n and m are valid. i.e. n > 0, m > 0.

Incomplete Code:
table = {} # table to memoize computed values

def num_of_paths(n, m):
# your code here
pass

Test Cases:

num_of_paths(1, 100) 1
num_of_paths(123, 1) 1
num_of_paths(3, 3) 6
num_of_paths(10, 10) 48620
num_of_paths(28, 56) 3438452994457305131328

Question

zrussel · Accepted Answer

Here is the implementation of the num_of_paths function using memoization:

table = {}

def num_of_paths(n, m):
# base cases
if n == 0 or m == 0:
return 1
if (n, m) in table:
return table[(n, m)]
# number of paths is the sum of paths from top and left cells
paths = num_of_paths(n - 1, m) + num_of_paths(n, m - 1)
table[(n, m)] = paths
return paths

print(num_of_paths(1, 100)) # 1
print(num_of_paths(123, 1)) # 1
print(num_of_paths(3, 3)) # 6
print(num_of_paths(10, 10)) # 48620
print(num_of_paths(28, 56)) # 3438452994457305131328

This function uses the fact that the number of paths to a cell is the sum of the number of paths from its top and left cells. The base cases are when either n or m is 0, in which case there is only 1 path (by definition). The function also uses a table dictionary to store the computed values to avoid recalculating them.

Answers

Related Questions

Answers

Answers

Answers

Answers

Answers