Динамическое программирование - Число различных комбинаций для достижения заданной оценка

Question

Рассмотрим игру, в которой игрок может набрать 3 или 5 или 10 очков в движении. Учитывая общий балл n, найдите число «отдельных» комбинаций, чтобы достичь заданного балла.

Мой код:

#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; 
} 

Для ввода 11, я получаю 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. Вы можете использовать кортежи, или просто вычислить уникальный индекс в м для каждой комбинации п и мин:

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

Зов первоначально с мин 1 (3 также будет работать, но 1 более общего назначения):

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