For each coin and its count, update the DP table by considering each valid usage of the coin (from 0 to counts[i]).

Approach

Construct an array dp where dp[i] denotes the number of distinct ways to form i.
Initialize dp[0] = 1 since there is one way to form amount 0 (by using no coins).
For every coin, iterate through the array dp in the reverse direction (to handle limited counts for each denomination).
For each amount j, iterate from 1 to counts[i] (representing the number of times we use the current coin) to calculate contributions.
Return dp[amount] as the final answer.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int numWays(vector<int>& coins, vector<int>& counts, int amount) {\n        vector<int> dp(amount + 1, 0);\n        dp[0] = 1;\n        \n        for (int i = 0; i < coins.size(); ++i) {\n            int coin = coins[i];\n

Related Tags