0457MediumArrayDynamic Programming

Slab Layouts Along A Path

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A yard sells paving slabs in the widths listed in widths, all different, and holds an unlimited number of each. A path of length span is laid by putting slabs down one after another from the gate outwards, and it counts as finished when the widths laid add up to exactly span.

Two layouts are the same only when they lay the same widths in the same order from the gate. So on a span of 5 with widths 2 and 3 available, laying 2 then 3 is one layout and laying 3 then 2 is a second.

Return how many layouts finish the path. Return 0 if none do. The count is guaranteed to fit in a signed 32-bit integer for every input you are given.

Examples

Example 1

Input: widths = [5, 7, 11], span = 22
Output: 5

Two slabs of 11 finish the path, and so does a run of three 5s together with one 7, which can be laid in four orders depending on where the 7 goes.

Example 2

Input: widths = [4, 6], span = 9
Output: 0

No run of 4s and 6s adds up to 9.

Example 3

Input: widths = [8], span = 24
Output: 1

Three 8s reach 24, and that is the only layout available.

Constraints

1 <= widths.length <= 200
1 <= widths[i] <= 1000
All the widths are distinct.
1 <= span <= 1000
The answer fits in a signed 32-bit integer.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def slab_layouts(widths: list[int], span: int) -> int:

Java

public int slabLayouts(int[] widths, int span)

The intended approach

Time O(span * k) for k stock widths.Space O(span) for the table of counts.

Count the layouts for every length from 0 up to the span, taking a length of 0 as one finished path, the empty one. A layout of length t is fixed by which slab lies furthest from the gate, and once that slab is chosen the rest is a layout of the shorter length t minus that width, so the counts for t add up the counts already computed for the shorter lengths.

Pythonentry point: slab_layouts

def slab_layouts(widths, span):
    # layouts[t] counts the ways to finish a path of length t. A layout is
    # settled by its final slab, so read the shorter answers off first.
    # O(span * k) time for k stock widths, O(span) space.
    layouts = [0] * (span + 1)
    layouts[0] = 1
    for t in range(1, span + 1):
        total = 0
        for w in widths:
            if w <= t:
                total += layouts[t - w]
        layouts[t] = total
    return layouts[span]

The obvious version

Grow every possible layout from the gate outwards, keeping only how much of the span is still open, and count the branches that land on exactly zero. Exponential in the span.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_slab_layouts(widths, span):
    count = 0
    stack = [span]
    while stack:
        left = stack.pop()
        if left == 0:
            count += 1
            continue
        for w in widths:
            if w <= left:
                stack.append(left - w)
    return count

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in