Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

How to count the number of non-overlapping/distinct sub-problems?

Правка en1, от CandidFlakes, 2023-08-13 19:32:06

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!

Теги dynamic programming, recursion, backtracking, sub-problems

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский CandidFlakes 2023-08-13 19:32:06 538 Initial revision (published)