Dynamic Programming - Number of distinct combinations to reach a given score

Question

Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of 'distinct' combinations to reach the given score.

My code:

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

For input 11, I am getting 3 as output but distinct combinations possible is only 1. (11 = 3 + 3 + 5)

How do I modify the above code to return the number of 'distinct' combination?

Answer 1

You can find the distinct combinations by enforcing a constraint that the elements in each combination must be monotonically increasing (i.e. each element is equal to or greater than the previous). So (3, 3, 5) is allowed but (3, 5, 3) and (5, 3, 3) are not. To implement this, just pass a minimum value to numOfWays, to indicate that all remaining values must be equal to or greater than this value.

int numOfWays(int n, int min){

Count the number of ways like this:

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;

You also need to consider the min when memoizing. You can use tuples, or just compute an unique index in m for every combination of n and min:

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

Call initially with a min of 1 (3 would also work but 1 is more general purpose):

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