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

## 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 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 = 2i <= ni++)
dp[i] += dp[i – 2];

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

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

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

cout<<ways(n)<<endl;

return 0;
}

`104`