#Problem:

Pascal’s triangle is a useful recursive definition that tells us the coefficients in the expansion of the polynomial (x + a)^n. Each element in the triangle has a coordinate, given by the row it is on and its position in the row (which you could call its column). Every number in Pascal’s triangle is defined as the sum of the item above it and the item that is directly to the upper left of it. If there is a position that does not have an entry, we treat it as if we had a 0 there. Below are the first few rows of the triangle:

Item: 0 1 2 3 4 5

Row 0: 1

Row 1: 1 1

Row 2: 1 2 1

Row 3: 1 3 3 1

Row 4: 1 4 6 4 1

Row 5: 1 5 10 10 5 1

 `...`

Define the procedure pascal(row, column) which takes a row and a column, and finds the value at that position in the triangle. Don’t use the closed-form solution, if you know it. def pascal(row, column)

#Solution:

def pascal(row, column):
 """
 >>> pascal(0, 0)
 1
 >>> pascal(5, 4)
 5
 >>> pascal(0, 1)
 0
 """
 if column == 0:
 return 1
 elif row == 0:
 return 0
 else:
 return pascal(row-1, column) + pascal(row-1, column-1)

Can we improve this code using memoization? because, pascal(5,4) = pascal (4, 4) + pascal(4, 3)

Problem:

Pascal’s triangle is a useful recursive definition that tells us the coefficients in the expansion of the polynomial (x + a)^n. Each element in the triangle has a coordinate, given by the row it is on and its position in the row (which you could call its column). Every number in Pascal’s triangle is defined as the sum of the item above it and the item that is directly to the upper left of it. If there is a position that does not have an entry, we treat it as if we had a 0 there. Below are the first few rows of the triangle:

Item: 0 1 2 3 4 5

Row 0: 1

Row 1: 1 1

Row 2: 1 2 1

Row 3: 1 3 3 1

Row 4: 1 4 6 4 1

Row 5: 1 5 10 10 5 1

 `...`

Define the procedure pascal(row, column) which takes a row and a column, and finds the value at that position in the triangle. Don’t use the closed-form solution, if you know it. def pascal(row, column)

Solution:

def pascal(row, column):
 """
 >>> pascal(0, 0)
 1
 >>> pascal(5, 4)
 5
 >>> pascal(0, 1)
 0
 """
 if column == 0:
 return 1
 elif row == 0:
 return 0
 else:
 return pascal(row-1, column) + pascal(row-1, column-1)

Can we improve this code using memoization? because, pascal(5,4) = pascal (4, 4) + pascal(4, 3)

def pascal_with_memoization(row, column):
 """
 >>> pascal_with_memoization(3, 2)
 3
 >>> pascal_with_memoization(3, 3)
 1
 >>> pascal_with_memoization(5,4)
 5
 """
 cache = {}
 for row_indx in range(0, row + 1):
 cache.setdefault(row_indx, []).insert(0, 1)
 for col_indx in range(1, column + 1):
 cache.setdefault(0, []).insert(col_indx, 0) 
 def pascal(row, column):
 if column == 0:
 return cache[row][column]
 elif row == 0:
 return cache[row][column]
  else:
 value_1 = 0
 value_2 = 0
 lst = cache[row-1]
 if len(lst) > column: 
 value_1 = cache[row-1][column]
 value_2 = cache[row-1][column-1]
 elif len(lst) > column - 1:
 value_1 = pascal(row-1, column)
 value_2 = cache[row-1][column-1] 
  cache.setdefault(row-1, []).insert(column, value_1)
 else:
 value_1 = pascal(row-1, column) value_2 = pascal(row-1, column-1)
 return value_1 + value_2
 return pascal(row, column)

Can we improve this code?

def pascal(row, column):
 """
 >>> pascal(0, 0)
 1
 >>> pascal(5,4)
 5
 >>> pascal(0, 1)
 0
 """
 if column == 0:
 return 1
 elif row == 0:
 return 0
 else:
 return pascal(row-1, column) + pascal(row-1, column-1)

Can we improve this code using memoization? because, pascal(5,4) = pascal (4, 4) + pascal(4, 3)

def pascal(row, column):
 """
 >>> pascal(0, 0)
 1
 >>> pascal(5,4)
 5
 >>> pascal(0, 1)
 0
 """
 if column == 0:
 return 1
 elif row == 0:
 return 0
 else:
 return pascal(row-1, column) + pascal(row-1, column-1)

Can we improve this code using memoization? because, pascal(5,4) = pascal (4, 4) + pascal(4, 3)

def pascal_with_memoization(row, column):
 """
 >>> pascal_with_memoization(3, 2)
 3
 >>> pascal_with_memoization(3, 3)
 1
 >>> pascal_with_memoization(5,4)
 5
 """
  cache = {}
 for row_indx in range(0, row + 1):
 cache.setdefault(row_indx, []).insert(0, 1)
 for col_indx in range(1, column + 1):
 cache.setdefault(0, []).insert(col_indx, 0) 
 def pascal(row, column):
 if column == 0:
 return cache[row][column]
 elif row == 0:
 return cache[row][column]
  else:
 value_1 = 0
 value_2 = 0
 lst = cache[row-1]
 if len(lst) > column: 
 value_1 = cache[row-1][column]
 value_2 = cache[row-1][column-1]
 elif len(lst) > column - 1:
 value_1 = pascal(row-1, column)
 value_2 = cache[row-1][column-1] 
  cache.setdefault(row-1, []).insert(column, value_1)
 else:
 value_1 = pascal(row-1, column) value_2 = pascal(row-1, column-1)
 return value_1 + value_2
 return pascal(row, column)

Can we improve this code?