Hitting the Exact Score

Hard

A contest has several kinds of tasks. Kind i is described by kinds[i] = [count, points]: there are count tasks of this kind, each worth points points. Count the ways to score exactly goal points. Tasks of the same kind are indistinguishable: only the number solved of each kind matters. For example, solving the first and second task of a kind is the same as solving the first and third. The answer can be large, so return it modulo 10⁹ + 7.

Example 1

goal=5, kinds=[[3, 1], [2, 2], [1, 4]] → 3

The ways are 1+2+2, 1+1+1+2 and 1+4. Five 1s are impossible since there are only three. That makes 3.

Example 2

goal=7, kinds=[[2, 3]] → 0

Tasks worth 3 give only 0, 3 or 6 points, so there is no way.

Constraints

1 ≤ goal ≤ 1000
1 ≤ len(kinds) ≤ 50
kinds[i] = [count, points], 1 ≤ count, points ≤ 50

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Water Between Walls Hard Biggest Solid Panel Block Hard Profit From Two Trades Hard Every Way to Space the Words Hard Crossing the Cave Hard

Input

goal=5, kinds=[[3, 1], [2, 2], [1, 4]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 81 tests on the server, hidden ones included.