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

December 7, 2021

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

In the count number of ways problem, we have to count distinct ways by which we can generate a given score. The problem has a dynamic programming solution. IN this article, we will provide a C++ solution with an explanation.

Count number of ways to reach a given score in a game problem desciption

Count number of ways Problem Description

Given a total score value. IN one move you can score 2,3 or 5. Find the number of distinct ways to reach the given total score. Two ways are different if they differ in count of 2,3 or 5.

Input:

  • First line contains integer n. The total score.

Output:

  • The number of ways.

Example

Input

  • 5

Output

  • 2

Explanation –

  • {5}, {2,3} are the only ways possible.

Count number of ways Problem Solution Explanation

It is given in the question that two ways are distinct only if they differ in count of 2,3 or 5. So we will first use 2, then 3 & then 5. After using one value we won’t use it again.

Time Complexity – O(n)
Space Complexity – O(n)

Code

#include <bits/stdc++.h>
using namespace std;
int ways(int n)
{
    int dp[n + 1] = {0};

    // Base Case
    dp[0] = 1;

    //using 2 only
    for (int i = 2; i <= n; i++)
        dp[i] += dp[i – 2];

    //using 3 only
    for (int i = 3; i <= n; i++)
        dp[i] += dp[i – 3];

    //using 5 only
    for (int i = 5; i <= n; i++)
        dp[i] += dp[i – 5];

    return dp[n];
}
int main()
{
    int n;
    cin >> n;

    cout<<ways(n)<<endl;

    return 0;
}

Output

10
4