Interval DP

Questions 1 to 5 of 8

1. 1. Matrix chain multiplication with sizes 10, 30, 5, 60 (the dims list). What is the cheapest number of multiplications for the whole chain?

   Type a number.

2. 2. In burst balloons, the inner loop tries every triple of positions l < k < r. An array of 100 balloons has 102 positions once the two sentinels are added. How many such triples are there in total, across all ranges?

   Type a number.

3. 3. What does this program print? ``python def max_coins(nums): n = len(nums) arr = [1] + nums + [1] dp = [[0] * (n + 2) for _ in range(n + 2)] for length in range(2, n + 2): for l in range(0, n + 2 - length): r = l + length best = 0 for k in range(l + 1, r): coins = dp[l][k] + dp[k][r] + arr[l] * arr[k] * arr[r] best = max(best, coins) dp[l][r] = best return dp[0][n + 1] print(max_coins([2, 3])) print(max_coins([1, 5])) ``

   9, then 10 (one per line)10, then 9 (one per line)9, then 9 (one per line)6, then 10 (one per line)
4. 4. What does this program print? Python ints have no fixed size. ``python print(100000 * 100000) ``

   -2147483648100000100000000001410065408
5. 5. Put the steps of the matrix chain program in the order it runs them.

   Use the arrows to put the steps in order.

   1. 1.Fill every range of two matrices, trying each split point↑↓
   2. 2.Read best[0][n - 1] as the cheapest cost for the whole chain↑↓
   3. 3.Fill every range of three matrices, then four, and so on up to n↑↓
   4. 4.Set best[i][i] to 0 for every single matrix↑↓