Get started

Number of Ways to Earn Points — Hard Problem & Solution

An exam has several types of question. types[i] = [counti, marksi] means there are counti questions of the i-th type, each worth marksi marks.

Problem statement

An exam has several types of question. types[i] = [count_i, marks_i] means there are count_i questions of the i-th type, each worth marks_i marks. Questions of the same type are indistinguishable.

Return the number of ways to earn exactly target marks, modulo 10^9 + 7.

Example 1

Input: target = 6, types = [[6,1],[3,2],[2,3]]
Output: 7

Example 2

Input: target = 5, types = [[50,1],[50,2],[50,5]]
Output: 4

Example 3

Input: target = 18, types = [[6,1],[3,2],[2,3]]
Output: 1
Explanation: Only answering every question reaches 18.

Constraints

  • 1 <= target <= 1000
  • n == types.length
  • 1 <= n <= 50
  • types[i].length == 2
  • 1 <= count_i, marks_i <= 50

How to solve Number of Ways to Earn Points

A bounded knapsack over question types. Because same-type questions are indistinguishable, a scheme is fully described by how many of each type it answers — so each type contributes one loop over its allowed counts.

Approach

  1. Start with dp[0] = 1.
  2. For each type (count, marks), build a fresh array: for every reachable total t and every c in 0 … count, add dp[t] into ndp[t + c·marks] while it stays within target.
  3. Return dp[target] at the end.

Why it works

Using a fresh array per type is what enforces the bound: without it, an in-place upward sweep would let a type be used unboundedly, and a downward sweep would cap it at one. Processing one type at a time in a fixed order counts each multiset of answers exactly once.

Complexity

  • Time — O(n · target · maxCount)
  • Space — O(target)

Pitfalls

  • An in-place sweep gives the unbounded or 0/1 knapsack, not the bounded one.
  • The target must be hit exactly; dp[target] is the answer, not a running sum.
  • Reduce modulo on every addition.

Reference solution

Python

from typing import List

def waysToReachTarget(target: int, types: List[List[int]]) -> int:
    MOD = 1000000007
    dp = [0] * (target + 1)
    dp[0] = 1
    for count, marks in types:
        ndp = [0] * (target + 1)
        for t in range(target + 1):
            if dp[t] == 0:
                continue
            c = 0
            while c <= count and t + c * marks <= target:
                ndp[t + c * marks] = (ndp[t + c * marks] + dp[t]) % MOD
                c += 1
        dp = ndp
    return dp[target]

JavaScript

var waysToReachTarget = function(target, types) {
    var MOD = 1000000007;
    var dp = [];
    for (var t0 = 0; t0 <= target; t0++) dp.push(0);
    dp[0] = 1;
    for (var i = 0; i < types.length; i++) {
        var count = types[i][0], marks = types[i][1];
        var ndp = [];
        for (var b = 0; b <= target; b++) ndp.push(0);
        for (var t = 0; t <= target; t++) {
            if (dp[t] === 0) continue;
            for (var c = 0; c <= count && t + c * marks <= target; c++) {
                ndp[t + c * marks] = (ndp[t + c * marks] + dp[t]) % MOD;
            }
        }
        dp = ndp;
    }
    return dp[target];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue