Grid paths and triangles

Questions 1 to 5 of 7

1. 1. A grid has 3 rows and 4 columns and no obstacles. Which expression gives the number of routes from the top-left cell to the bottom-right cell?

   C(7, 3) = 35C(5, 2) = 10C(6, 3) = 20C(4, 2) = 6
2. 2. What does this program print? ``cpp #include <iostream> int main() { int grid[3][4] = { {0, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 0, 0}, }; long long ways[3][4] = {}; for (int r = 0; r < 3; ++r) for (int c = 0; c < 4; ++c) { if (grid[r][c] == 1) ways[r][c] = 0; else if (r == 0 && c == 0) ways[r][c] = 1; else ways[r][c] = (r > 0 ? ways[r - 1][c] : 0) + (c > 0 ? ways[r][c - 1] : 0); } std::cout << ways[2][3] << "\n"; } ``

   2354
3. 3. Which statements about the one-row version of the grid table are true?

   Pick every answer that is true.

   It keeps one row and fills columns from left to rightIt gives different answers from the two-row versionWhen column c is reached, row[c] still holds the value from the row aboveIt stores the whole two-dimensional table
4. 4. Why does the lesson say a table is needed once any cell is blocked?

   The binomial formula gives a wrong answer for every grid, even an open oneSubtracting the routes through each obstacle counts a route through two obstacles twice, and the fix needs longer sums as obstacles growThe table is faster than the formula on every gridThe formula cannot read the rows and columns of a grid with a blocked cell
5. 5. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <vector> int main() { std::vector<std::vector<int>> t = {{1}, {8, 2}, {4, 9, 5}}; std::vector<int> best = t.back(); for (int r = static_cast<int>(t.size()) - 2; r >= 0; --r) for (int c = 0; c <= r; ++c) best[c] = t[r][c] + std::min(best[c], best[c + 1]); std::cout << best[0] << "\n"; } ``

   412813