0729HardArrayDynamic Programming

Restoring The Panel Gallery

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 gallery has n panels waiting to be restored and a shortlist of exactly n paid restorers, both numbered 0 through n - 1. Restorer i needs hours[i] whole hours to bring one panel back and charges fee[i] for the job. A restorer may be hired for at most one panel, and you may hire as few or as many of them as you like.

One volunteer is also available. The volunteer restores a panel in exactly one hour and charges nothing.

The work runs in whole hours, one after another. The paid restorers you hire work in sequence, in whatever order you choose, each occupying the workshop for their own number of hours. The volunteer may work during an hour when a paid restorer is at work in the workshop, restoring one panel in that hour, and may not work during any other hour.

Every panel has to be restored by exactly one worker, paid or volunteer. Return the smallest total fee that gets all n panels restored.

Examples

Example 1

Input: fee = [3, 2, 2, 2], hours = [8, 1, 1, 1]
Output: 3

Hire restorer 0 alone for 3. It restores one panel and occupies the workshop for 8 hours, and the volunteer restores the other three panels in three of those hours.

Example 2

Input: fee = [1, 100], hours = [1, 100]
Output: 1

Hire restorer 1 for 100. It restores one panel and holds the workshop for 100 hours, and the volunteer restores the remaining panel in the first of them.

Example 3

Input: fee = [7], hours = [1]
Output: 7

There is one panel and the volunteer cannot work unless a paid restorer is in the workshop, so restorer 0 has to be hired for 7.

Constraints

1 <= fee.length <= 500
hours.length == fee.length
1 <= fee[i] <= 10^6
1 <= hours[i] <= 500

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 least_restoration_fee(fee: list[int], hours: list[int]) -> int:

Java

public int leastRestorationFee(int[] fee, int[] hours)

The intended approach

Time O(n^2) for n panels: one downward sweep of an (n + 1)-entry table per restorer.Space O(n) for the table.

Hiring restorer `i` disposes of its own panel and, while it occupies the workshop, leaves `hours[i]` hours in which the volunteer can dispose of one panel each, so a hire accounts for `hours[i] + 1` panels at a price of `fee[i]`. That turns the job into picking a subset of the restorers whose accounted panels reach `n` at the lowest total price. Keep a table of the cheapest price that accounts for each number of panels from `0` to `n`, clamping anything past `n` down to `n`, and fold the restorers in one at a time while walking the table from high to low so no restorer is counted twice. The entry for `n` is the answer, and it is always reachable because hiring everybody accounts for at least `2n` panels.

Pythonentry point: least_restoration_fee

def least_restoration_fee(fee, hours):
    # Hiring restorer i settles its own panel and, on top of that, keeps the yard
    # busy for hours[i] further hours, so a hire is an item that accounts for
    # hours[i] + 1 panels at a price of fee[i].  Fill a table over "panels
    # accounted for", capped at n because anything beyond n is no better, walking
    # the table downwards so each restorer is hired at most once.
    # Time O(n^2).  Space O(n).
    n = len(fee)
    unreachable = float("inf")
    best = [0] + [unreachable] * n
    for i in range(n):
        span = hours[i] + 1
        for covered in range(n, 0, -1):
            earlier = covered - span
            if earlier < 0:
                earlier = 0
            candidate = best[earlier] + fee[i]
            if candidate < best[covered]:
                best[covered] = candidate
    return best[n]

The obvious version

Try every subset of the restorers. A subset works when the number hired plus the hours they occupy the workshop for is at least the number of panels. Keep the cheapest subset that works.

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_least_restoration_fee(fee, hours):
    n = len(fee)
    best = None
    for mask in range(1 << n):
        paid_hours = 0
        hired = 0
        total = 0
        for i in range(n):
            if mask & (1 << i):
                paid_hours += hours[i]
                hired += 1
                total += fee[i]
        if hired + paid_hours >= n:
            if best is None or total < best:
                best = total
    return best

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