동적 프로그래밍 - 주어진 점수에 도달하기위한 고유 한 조합 수

Question

플레이어는 이동 중에 3 점 또는 5 점 또는 10 점을 얻을 수있는 게임을 고려하십시오. 총 점수 n이 주어지면 주어진 점수에 도달하는 '고유 한'조합 수를 찾습니다.

내 코드

:

입력은 11

#include <iostream> 
#include<unordered_map> 
using namespace std; 

unordered_map<int,int> m; 

int numOfWays(int n){ 
    if(n==0) 
     return 1; 
    if(n<0) 
     return 0; 
    if(m[n]>0) 
     return m[n]; 
    m[n] = numOfWays(n-3)+numOfWays(n-5)+numOfWays(n-10); 
    return m[n]; 
} 

int main(){ 
    int t; 
    cin>>t; 
    cout<<numOfWays(t)<<endl; 
    return 0; 
} 

, I 출력 만 가능한 별개의 조합으로 3 얻고 단지 내가이를 수정하려면 어떻게 1 (11 = 3 + 3 + 5)

입니다 '뚜렷한'조합의 수를 반환하는 코드?

Answer 1

각 조합의 요소가 단조롭게 증가해야한다는 제약 조건 (예 : 각 요소가 이전보다 크거나 같음)을 적용하여 고유 한 조합을 찾을 수 있습니다. 따라서 (3, 3, 5)는 허용되지만 (3, 5, 3) 및 (5, 3, 3)은 허용되지 않습니다. 이것을 구현하려면 numOfWays에 최소값을 전달하여 나머지 값이 모두이 값 이상이어야 함을 나타냅니다.

int numOfWays(int n, int min){ 

이 같은 방법의 수를 계산 :

int ways = 0; 
if(min <= 3) 
    ways += numOfWays(n-3, 3); 
if(min <= 5) 
    ways += numOfWays(n-5, 5); 
if(min <= 10) 
    ways += numOfWays(n-10, 10); // from now on elements must be 10 or greater 
m[index] = ways; 

는 또한 memoizing 때 분을 고려해야합니다. 당신은 튜플을 사용하거나 n 및 분의 모든 조합에 대한 m의 고유 인덱스를 계산할 수 : 1의 분에 처음

int index = (n * 10) + min; 
if(m[index]>0) 
    return m[index]; 

전화 (도 작동 할 3 만 1보다 일반적인 목적이다) :

cout<<numOfWays(t,1)<<endl;