Problem

There is a test that has n types of questions. You are given an integer target and a 0-indexed 2D integer array types where types[i] = [counti, marksi] indicates that there are counti questions of the ith type, and each one of them is worth marksi points.

Return _the number of ways you can earnexactly _target points in the exam. Since the answer may be too large, return it modulo 10^9 + 7.

Note that questions of the same type are indistinguishable.

  • For example, if there are 3 questions of the same type, then solving the 1st and 2nd questions is the same as solving the 1st and 3rd questions, or the 2nd and 3rd questions.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: target = 6, types = [[6,1],[3,2],[2,3]]
Output: 7
Explanation: You can earn 6 points in one of the seven ways:
- Solve 6 questions of the 0th type: 1 + 1 + 1 + 1 + 1 + 1 = 6
- Solve 4 questions of the 0th type and 1 question of the 1st type: 1 + 1 + 1 + 1 + 2 = 6
- Solve 2 questions of the 0th type and 2 questions of the 1st type: 1 + 1 + 2 + 2 = 6
- Solve 3 questions of the 0th type and 1 question of the 2nd type: 1 + 1 + 1 + 3 = 6
- Solve 1 question of the 0th type, 1 question of the 1st type and 1 question of the 2nd type: 1 + 2 + 3 = 6
- Solve 3 questions of the 1st type: 2 + 2 + 2 = 6
- Solve 2 questions of the 2nd type: 3 + 3 = 6

Example 2

1
2
3
4
5
6
7

Input: target = 5, types = [[50,1],[50,2],[50,5]]
Output: 4
Explanation: You can earn 5 points in one of the four ways:
- Solve 5 questions of the 0th type: 1 + 1 + 1 + 1 + 1 = 5
- Solve 3 questions of the 0th type and 1 question of the 1st type: 1 + 1 + 1 + 2 = 5
- Solve 1 questions of the 0th type and 2 questions of the 1st type: 1 + 2 + 2 = 5
- Solve 1 question of the 2nd type: 5

Example 3

1
2
3

Input: target = 18, types = [[6,1],[3,2],[2,3]]
Output: 1
Explanation: You can only earn 18 points by answering all questions.

Constraints

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

Solution

Method 1 – Dynamic Programming (Knapsack)

Intuition

This is a variation of the bounded knapsack problem. For each type, you can pick 0 to counti questions, each worth marksi points. Use DP to count the number of ways to reach exactly target points.

Approach

  1. Let dp[i] be the number of ways to get i points.
  2. Initialize dp[0] = 1 (one way to get 0 points).
  3. For each type, for each possible number of questions (from 1 to counti), update dp from high to low to avoid overcounting.
  4. Return dp[target].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int waysToReachTarget(int target, vector<vector<int>>& types) {
        const int mod = 1e9+7;
        vector<int> dp(target+1);
        dp[0] = 1;
        for (auto& t : types) {
            int cnt = t[0], mark = t[1];
            vector<int> ndp = dp;
            for (int i = 1; i <= cnt; ++i) {
                for (int j = target; j >= i*mark; --j) {
                    ndp[j] = (ndp[j] + dp[j-i*mark]) % mod;
                }
            }
            dp = ndp;
        }
        return dp[target];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func waysToReachTarget(target int, types [][]int) int {
    mod := int(1e9+7)
    dp := make([]int, target+1)
    dp[0] = 1
    for _, t := range types {
        cnt, mark := t[0], t[1]
        ndp := make([]int, target+1)
        copy(ndp, dp)
        for i := 1; i <= cnt; i++ {
            for j := target; j >= i*mark; j-- {
                ndp[j] = (ndp[j] + dp[j-i*mark]) % mod
            }
        }
        dp = ndp
    }
    return dp[target]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int waysToReachTarget(int target, int[][] types) {
        int mod = 1_000_000_007;
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int[] t : types) {
            int cnt = t[0], mark = t[1];
            int[] ndp = dp.clone();
            for (int i = 1; i <= cnt; i++) {
                for (int j = target; j >= i*mark; j--) {
                    ndp[j] = (ndp[j] + dp[j-i*mark]) % mod;
                }
            }
            dp = ndp;
        }
        return dp[target];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun waysToReachTarget(target: Int, types: Array<IntArray>): Int {
        val mod = 1_000_000_007
        var dp = IntArray(target+1)
        dp[0] = 1
        for (t in types) {
            val cnt = t[0]; val mark = t[1]
            val ndp = dp.copyOf()
            for (i in 1..cnt) {
                for (j in target downTo i*mark) {
                    ndp[j] = (ndp[j] + dp[j-i*mark]) % mod
                }
            }
            dp = ndp
        }
        return dp[target]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def waysToReachTarget(self, target: int, types: list[list[int]]) -> int:
        mod = 10**9+7
        dp = [0]*(target+1)
        dp[0] = 1
        for cnt, mark in types:
            ndp = dp[:]
            for i in range(1, cnt+1):
                for j in range(target, i*mark-1, -1):
                    ndp[j] = (ndp[j] + dp[j-i*mark]) % mod
            dp = ndp
        return dp[target]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn ways_to_reach_target(target: i32, types: Vec<Vec<i32>>) -> i32 {
        let target = target as usize;
        let modulo = 1_000_000_007;
        let mut dp = vec![0; target+1];
        dp[0] = 1;
        for t in types.iter() {
            let cnt = t[0] as usize;
            let mark = t[1] as usize;
            let mut ndp = dp.clone();
            for i in 1..=cnt {
                for j in (i*mark..=target).rev() {
                    ndp[j] = (ndp[j] + dp[j-i*mark]) % modulo;
                }
            }
            dp = ndp;
        }
        dp[target]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    waysToReachTarget(target: number, types: number[][]): number {
        const mod = 1_000_000_007
        let dp = new Array(target+1).fill(0)
        dp[0] = 1
        for (const [cnt, mark] of types) {
            const ndp = dp.slice()
            for (let i = 1; i <= cnt; i++) {
                for (let j = target; j >= i*mark; j--) {
                    ndp[j] = (ndp[j] + dp[j-i*mark]) % mod
                }
            }
            dp = ndp
        }
        return dp[target]
    }
}

Complexity

  • ⏰ Time complexity: O(n * target * max_count), where n is the number of types and max_count is the maximum counti.
  • 🧺 Space complexity: O(target), for the DP array.