I am trying to solve this problem using DP.
I am able to observe that if I approach it using recursive backtracking, then there are 20^20(20*20*20..... 20 times for each garment) sub-problems, including overlapping sub-problems. Also, the total spending can be anything from 0 to 200(both inclusive).
How can I calculate the number of non-overlapping sub-problems for this problem?
I will be thankful for any help!
The DP for this problem looks like this: $$$\mathrm{dp}[i][j]$$$ is a boolean representing "is it possible to buy each of one of the first $$$i$$$ garments, spending $$$j$$$ amount money". Since $$$0 \le i \le M$$$ and $$$0 \le j \le C$$$ you get that there are $$$(M + 1)(C + 1)$$$ states (subproblems).