1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <vector>

const int M = 1'000'000'007;

class Solution {
public:
    int waysToReachTarget(int target, std::vector<std::vector<int>>& types) {
        std::vector<int> dp(target + 1);
        dp[0] = 1;
        for (auto& type : types) {
            int m = type[1];
            for (int i = target; i >= m; --i) {
                for (int c = 1; c <= type[0]; ++c) {
                    int j = i - c * m;
                    if (j >= 0) {
                        dp[i] = (dp[i] + dp[j]) % M;
                    }
                }
            }
        }
        return dp.back();
    }
};