Count number of ways to reach a given score in a game - GeeksforGeeks

Count number of ways to reach a given score in a game - GeeksforGeeks
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 ways to reach the given score.

This problem is a variation of coin change problem and can be solved in O(n) time and O(n) auxiliary space.

The idea is to create a table of size n+1 to store counts of all scores from 0 to n. For every possible move (3, 5 and 10), increment values in table.

int count(int n)

{

    // table[i] will store count of solutions for

    // value i.

    int table[n+1], i;

 

    // Initialize all table values as 0

    memset(table, 0, sizeof(table));

 

    // Base case (If given value is 0)

    table[0] = 1;

 

    // One by one consider given 3 moves and update the table[]

    // values after the index greater than or equal to the

    // value of the picked move

    for (i=3; i<=n; i++)

       table[i] += table[i-3];

    for (i=5; i<=n; i++)

       table[i] += table[i-5];

    for (i=10; i<=n; i++)

       table[i] += table[i-10];

 

    return table[n];

}

http://ideone.com/qRHqbc

1. std::vector<int> moves = { 3, 5, 10 };
2. std::vector<int> c(n + 1, 0);
3. c[0] = 1;
4. for (int m : moves) for (size_t i = m; i <= n; ++i) c[i] += c[i - m];

DP-Memonization
http://ideone.com/8KL0Wd

1. int solve(int n) {
2. if(n < 0) {
3. return 0;
4. }
5. if(dp[n] != -1) {
6. return dp[n];
7. } else {
8. return dp[n] =(solve(n-10) + solve(n-3) + solve(n-5));
9. }
10. }

Coin change: http://massivealgorithms.blogspot.com/2014/06/dynamic-programming-set-7-coin-change.html
Read full article from Count number of ways to reach a given score in a game - GeeksforGeeks