동전이라는 값 목록과 같은 길이의 수량이라는 또 다른 목록이 있다고 가정합니다. i번째 코인의 가치는 코인[i]이고 현재 i번째 코인의 수량[i]개를 가지고 있습니다. 이 코인의 비어 있지 않은 그룹을 사용하여 얻을 수 있는 고유한 코인 합계 값의 수를 찾아야 합니다.
따라서 입력이 동전 =[1, 2, 5] 수량 =[1, 2, 1]과 같으면 다음과 같은 고유한 동전 합계 [1] =1, [2]를 가질 수 있으므로 출력은 10이 됩니다. =2, [1,2] =3, [2,2] =4, [5] =5, [1,5] =6, [2,5] =7, [1,2,5] =8 , [2,2,5] =9, [1,2,2,5] =10.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
함수 rec() 를 정의하십시오. 이것은 내가, res
를 취할 것입니다if i is same as size of coins , then return for k in range 0 to quantities[i] + 1, do cur := res + k * coins[i] insert cur into fres rec(i + 1, cur) From the main method, do the following: fres := a new set rec(0, 0) return size of fres - 1
예시
class Solution: def solve(self, coins, quantities): def rec(i, res): if i == len(coins): return for k in range(0, quantities[i] + 1): cur = res + k * coins[i] fres.add(cur) rec(i + 1, cur) fres = set() rec(0, 0) return len(fres) - 1 ob = Solution() coins = [1, 2, 5] quantities = [1, 2, 1] print(ob.solve(coins, quantities))
입력
[1, 2, 5], [1, 2, 1]
출력
10