Number of Ways to Earn Points

Number of Ways to Earn Points

What is this problem about?

The Number of Ways to Earn Points problem gives you a list of tasks, each with a maximum count and a score. You want to earn exactly a target number of points. Count the number of ways to select tasks (picking each task type between 0 and its max count times) to hit the target exactly. This is a bounded knapsack counting problem.

Why is this asked in interviews?

TuSimple asks this because it's a clean extension of the 0/1 knapsack to bounded quantities. The key distinction from unbounded knapsack: each task type has a maximum count. The array and dynamic programming interview pattern is demonstrated through the bounded knapsack variant.

Algorithmic pattern used

Bounded knapsack DP. dp[j] = number of ways to earn exactly j points. For each task type (count c, score s): update DP in reverse (0/1 knapsack style, but for bounded count). For each number of uses u from 1 to c: dp[j] += dp[j-u*s]. Or use the sliding window optimization for O(target * n) time.

Example explanation

tasks=[(3,1),(2,2)], target=4. (Can use type1 up to 3 times at 1 point each, type2 up to 2 times at 2 points each.) After type1: dp = [1,1,1,1,0] (ways to earn 0..4 using type1). After type2:

• Use 0 type2: dp[0..4]=[1,1,1,1,0].
• Use 1 type2 (add 2): dp[2]+=dp[0]=1, dp[3]+=dp[1]=1, dp[4]+=dp[2]=1+1=2.
• Use 2 type2 (add 4): dp[4]+=dp[0]=1. dp[4] = 0+1+1+... = 4 ways total.

Common mistakes candidates make

• Using unbounded knapsack instead of bounded (ignoring max count).
• Updating DP in forward order for bounded 0/1 items (must process in reverse or use auxiliary array).
• Not initializing dp[0]=1.
• Off-by-one in the maximum usage count loop.

Interview preparation tip

Bounded knapsack counting is more complex than 0/1 or unbounded variants. The standard approach loops over each item type and each usage count. For efficiency with large counts, use the sliding window deque optimization to compute the DP for each item in O(target) time regardless of max count. Practice all three knapsack variants (0/1, bounded, unbounded) to handle any variant that appears in interviews.