Grid paths and triangles

Questions 1 to 5 of 7

1. 1. A 3 by 3 grid has its centre cell blocked. The robot moves only right or down, from the top-left corner to the bottom-right corner. How many routes are there?

   6420
2. 2. In the bottom-up triangle method, why must the inner loop of each row run from left to right?

   Python lists can only be filled from index 0 upwardsThe answer sits in the bottom row, so that row must be filled firstThe row length changes when the loop goes from right to leftbest[c + 1] must still hold the row below when best[c] reads it
3. 3. Which statements about counting routes and the grid table are true? Pick all that apply.

   Pick every answer that is true.

   The formula C(S, R - 1) gives the right count even when some cells are blockedA blocked start cell gives a count of 0 for the whole gridThe rolling version keeps one row of counts instead of one list per rowWhen a count passes 9.2 quintillion, Python throws an exceptionA 5 by 5 grid with no blocked cells has C(8, 4) = 70 routes
4. 4. Which statements about the minimum path sum and the triangle are true? Pick all that apply.

   Pick every answer that is true.

   Always stepping to the cheaper neighbour finds the cheapest grid routeIn the grid table, the top row takes each value only from its left neighbourThe bottom-up triangle method needs one list as long as the bottom row, and reads the answer from best[0]Walking each triangle row from right to left gives the correct answer on the lesson's exampleThe rolling grid version needs one list for every row of the grid
5. 5. What does this program print? ``python def min_total_bottom_up(triangle): rows = len(triangle) best = list(triangle[-1]) for r in range(rows - 2, -1, -1): row = triangle[r] for c in range(len(row)): best[c] = row[c] + min(best[c], best[c + 1]) return best[0] tri = [[5], [9, 2], [1, 7, 3]] print(f"answer = {min_total_bottom_up(tri)}") ``

   answer = 10answer = 8answer = 7answer = 12