DP bug hunt

Questions 1 to 5 of 8

1. 1. Coin change with coins [1, 2, 5] and amount 5 should print 4, but this code prints 0. Which line is the bug? ``python coins = [1, 2, 5] amount = 5 ways = [0] * (amount + 1) ways[0] = 0 for coin in coins: for a in range(coin, amount + 1): ways[a] += ways[a - coin] print(ways[amount]) ``

   The inner loop should start at a = 0, not a = coinways[0] = 0 should be ways[0] = 1, because the empty set of coins is one way to make amount 0[0] * (amount + 1) should be [0] * amountThe coins must be sorted before the loop runs
2. 2. The minimum path sum for the grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]] should be 7, but this code prints 2. Which is the bug? ``python grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]] rows = len(grid) cols = len(grid[0]) dp = [[0] * cols for _ in range(rows)] dp[0][0] = grid[0][0] for i in range(1, rows): for j in range(1, cols): dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]) print(dp[rows - 1][cols - 1]) ``

   The first row and first column are never written, so they stay 0, and the minimum picks a 0 that is not a real costThe min should be maxdp[0][0] should be 1The loops should start at i = 0 and j = 0
3. 3. One item with weight 2 and value 3, and capacity 5, should give 3, but this code prints 6. Which is the bug? ``python weights = [2] values = [3] capacity = 5 best = [0] * (capacity + 1) for item in range(len(weights)): w = weights[item] v = values[item] for c in range(w, capacity + 1): best[c] = max(best[c], best[c - w] + v) print(best[capacity]) ``

   best should be a set, not a listThe answer should be best[0], not best[capacity]best[c - w] is read after this item has already updated it, so the item is used twice; the loop over c should run from capacity down to wThe inner loop should start at c = 0
4. 4. With coins [1, 2, 5] and amount 5, this code raises IndexError: list index out of range. Which is the bug? ``python coins = [1, 2, 5] amount = 5 ways = [0] * amount ways[0] = 1 for coin in coins: for a in range(coin, amount + 1): ways[a] += ways[a - coin] ``

   The base case should be ways[0] = 0The loop should stop at a < amountThe coins list must be sorted before the loopThe list is sized amount, so its cells are 0 to amount - 1 and there is no cell for amount; it should be [0] * (amount + 1)
5. 5. What does this program print? ``python nums = [-3, -1, -2] current = 0 best = 0 for x in nums: current = max(x, current + x) best = max(best, current) print('largest sum of a run:', best) ``

   largest sum of a run: 0largest sum of a run: -1largest sum of a run: -2largest sum of a run: -3