Number of ways to earn points

Array Dynamic Programming

59.5% acceptance

Feb 25, 2026

506

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 earn exactly target points in the exam. Since the answer may be too large, return it modulo 109 + 7. Note that questions of the same type are indistinguishable.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn ways_to_reach_target(target: i32, types: Vec<Vec<i32>>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let target = target as usize;
    let mut dp = vec![0i64; target + 1];
    dp[0] = 1;
    for t in &types {
      let (cnt, marks) = (t[0] as usize, t[1] as usize);
      let mut new_dp = vec![0i64; target + 1];
      for j in 0..=target {
        let max_c = (j / marks).min(cnt);
        for c in 0..=max_c {
          new_dp[j] = (new_dp[j] + dp[j - c * marks]) % MOD;
        }
      }
      dp = new_dp;
    }
    dp[target] as i32
  }
}