Pyramid of Shards

A pyramid of crystal shards is given as rows, where rows[i] holds i + 1 integers. A collector starts at the single apex shard rows[0][0] and descends: from position j in one row they may move to position j or j + 1 in the row below. Every visited shard's value is added to the score (values may be negative). Return the minimum possible score when reaching the bottom row.

Examples

Input:  rows = [[4],
                [2, 7],
                [6, 1, 9],
                [5, 3, 8, 2]]
Output: 10
Explanation: 4 -> 2 -> 1 -> 3.

Input:  rows = [[-5]]
Output: -5

Constraints

• 1 <= len(rows) <= 300, len(rows[i]) == i + 1
• -10**4 <= rows[i][j] <= 10**4
• Target complexity: O(n2) for n rows; trying every one of the 2(n-1) descents is impossible.

Goals

• Fill a table whose rows have different lengths
• Recognise that computing from the bottom row upwards avoids boundary checks