DP bug hunt

Questions 1 to 5 of 8

1. 1. The function should return 4 for n = 3, but it returns 3. What is the bug? ``cpp // Ways to climb n steps, taking 1, 2 or 3 steps at a time long long climb(int n) { std::vector<long long> ways(n + 1, 0); ways[0] = 0; ways[1] = 1; ways[2] = 2; for (int i = 3; i <= n; ++i) { ways[i] = ways[i - 1] + ways[i - 2] + ways[i - 3]; } return ways[n]; } ``

   The loop should stop at n - 1ways[0] should be 1, because taking no steps is one way, and ways[3] reads ways[0]ways[2] should be 0, because two steps cannot be taken on their ownThere is no bug, since 3 is the number of ways to climb 3 steps
2. 2. Which part of this code gives wrong counts? ``cpp // Paths from the top-left to the bottom-right corner, moving right or down std::vector<std::vector<long long>> ways(rows, std::vector<long long>(cols, 1)); for (int r = 1; r < rows; ++r) { for (int c = cols - 1; c >= 1; --c) { ways[r][c] = ways[r - 1][c] + ways[r][c - 1]; } } ``

   The first row and column are set to 1 instead of 0The outer loop should start at r = 0A vector of vectors cannot hold a grid of countsThe inner loop runs right to left, so ways[r][c - 1] still holds the old value when ways[r][c] is computed
3. 3. Which bug is in this function? ``cpp // Fewest coins that make amount std::vector<int> fewest(amount + 1, 0); // 0 means 'not reached' for (int a = 1; a <= amount; ++a) { int best = 0; for (int c : coins) { if (c <= a && (best == 0 || fewest[a - c] + 1 < best)) { best = fewest[a - c] + 1; } } fewest[a] = best; } return fewest[amount]; ``

   The outer loop should run over coins and the inner loop over amountsThe loop should count amounts from amount down to 10 is both the starting value and the 'not reached' marker, so an amount that cannot be made acts like it was made with 0 coins, and 0 + 1 becomes a candidateThe coins must be sorted before the loop starts
4. 4. What happens when this program runs? ``cpp #include <iostream> #include <vector> int main() { int n = 3; std::vector<long long> ways(n + 1, 0); ways[0] = 1; ways[1] = 1; for (int i = 0; i <= n; ++i) { ways.at(i) = ways.at(i - 1) + ways.at(i - 2); } std::cout << ways.at(n) << '\n'; } ``

   It stops with std::out_of_range, because i - 1 and i - 2 are negative at i = 0 and .at() rejects the huge unsigned indexIt prints 5, which is the number of ways to climb 3 stepsIt silently reads memory before the vector and prints a garbage numberIt prints 0, because ways[0] is overwritten with 0
5. 5. What does this program print? ``cpp #include <iostream> #include <vector> int main() { const int rows = 2; const int cols = 4; std::vector<long long> row(cols, 1); for (int r = 1; r < rows; ++r) { for (int c = cols - 1; c >= 1; --c) { row[c] += row[c - 1]; } } std::cout << row[cols - 1] << '\n'; } ``

   4231