Number of Ways to Earn Points

hard dp knapsack

Problem

A test has types of questions. types[i] = [count_i, marks_i] means there are count_i questions each worth marks_i points. Solving a question gives all its marks; questions of the same type are indistinguishable. Return the number of ways to earn exactly target points, modulo 10^9 + 7.

Inputtarget = 6, types = [[6,1],[3,2],[2,3]]

Output7

dp[t] = ways to reach t points. For each type, dp[t] += dp[t − k·marks] for k = 1..count.

target

types (count:marks, …)

def ways_to_reach_target(target, types):
    MOD = 10**9 + 7
    dp = [0] * (target + 1)
    dp[0] = 1
    for count, marks in types:
        # iterate points downward (0/1 per copy of this type)
        for t in range(target, 0, -1):
            for k in range(1, count + 1):
                if k * marks > t:
                    break
                dp[t] = (dp[t] + dp[t - k * marks]) % MOD
    return dp[target]

function waysToReachTarget(target, types) {
  const MOD = 1000000007;
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (const [count, marks] of types) {
    for (let t = target; t >= 1; t--) {
      for (let k = 1; k <= count; k++) {
        if (k * marks > t) break;
        dp[t] = (dp[t] + dp[t - k * marks]) % MOD;
      }
    }
  }
  return dp[target];
}

class Solution {
    public int waysToReachTarget(int target, int[][] types) {
        int MOD = 1_000_000_007;
        long[] dp = new long[target + 1];
        dp[0] = 1;
        for (int[] type : types) {
            int count = type[0], marks = type[1];
            for (int t = target; t >= 1; t--) {
                for (int k = 1; k <= count; k++) {
                    if (k * marks > t) break;
                    dp[t] = (dp[t] + dp[t - k * marks]) % MOD;
                }
            }
        }
        return (int) dp[target];
    }
}

int waysToReachTarget(int target, vector<vector<int>>& types) {
    const long long MOD = 1000000007LL;
    vector<long long> dp(target + 1, 0);
    dp[0] = 1;
    for (auto& type : types) {
        int count = type[0], marks = type[1];
        for (int t = target; t >= 1; t--) {
            for (int k = 1; k <= count; k++) {
                if (k * marks > t) break;
                dp[t] = (dp[t] + dp[t - k * marks]) % MOD;
            }
        }
    }
    return (int) dp[target];
}

Explanation

Each question type is a "stack" of identical items: up to count copies, each adding marks points. We want the number of ways to hit target exactly — a bounded knapsack counting problem.

Let dp[t] = the number of ways to score exactly t points using the types processed so far. We start with dp[0] = 1: there is one way to score zero — answer nothing.

For a type with (count, marks) we update dp, but we must use each type only once. We iterate the points t from target downward so that within this type's update we never reuse the just-written values. For each t we try taking k = 1, 2, …, count questions of this type and add dp[t - k·marks].

The inner break stops as soon as k·marks exceeds t, since no larger k can fit. All sums are taken modulo 10^9 + 7. After all types are folded in, dp[target] is the answer.

Example: target = 6, types = [[6,1],[3,2],[2,3]]. Folding the three types gives dp[6] = 7 distinct ways to reach 6 points.

Time: O(target · Σ count_i) Space: O(target)