Press parentheses: Proof strip
Inputs
readings is a list of positive whole numbers that describe matrix sizes.
Your tasks
- Create a list
leastCosts.readingslists matrix sizes. A matrix is a table of numbers with rows and columns. Matrix 0 hasreadings[0]rows andreadings[1]columns. Matrix 1 hasreadings[1]rows andreadings[2]columns, and so on. Multiplying an a-by-b matrix by a b-by-c matrix costs a * b * c number multiplications. You may group the matrices with brackets, but must keep their order. Different groups can have different costs. For the first matrix alone, record 0. Then record the least total cost for the first two matrices, the first three, and so on. Fewer than two size numbers means there are no matrices, soleastCostsis empty. - Complete
pressParenthesesProofStripso it returnsleastCosts. Return it, do not print it.
Example
If readings is [10, 4, 4, 7, 8], then leastCosts is [0, 160, 392, 656] and pressParenthesesProofStrip returns [0, 160, 392, 656].
Rules
- If
leastCostsis empty, return [].
Test data
TEST DATA 1: readings is [9, 9, 5, 4, 1].
TEST DATA 2: readings is [8, 8, 8, 10].
Examples
Input: readings = [9,9,5,4,1] Output: [0,405,504,146]
leastCosts is [0, 405, 504, 146]. pressParenthesesProofStrip returns that whole list, so return [0, 405, 504, 146].
Input: readings = [8,8,8,10] Output: [0,512,1152]
leastCosts is [0, 512, 1152]. pressParenthesesProofStrip returns that whole list, so return [0, 512, 1152].
Input: readings = [] Output: []
leastCosts is []. pressParenthesesProofStrip returns that whole list, so return [].
Input limits
- 0 <= input size <= 16.
- Answers fit in a signed 32-bit integer: -2,147,483,648 through 2,147,483,647.
- Every dimension is an integer from 1 through 10; there are at most 16 dimensions.
Efficiency goal
Big-O describes how the work or memory needed grows as the input gets larger.
Efficiency goal: time O(n^3); extra memory, including the helper list, O(n^2). n is the input length. These labels describe how work and memory grow with the input.
Practice focus
Build leastCosts first, then return exactly what the tasks ask for. Follow the order, keep repeated values when the rule says so, and check the empty case.