Count Number of Ways to Reach a Given Score Problem

This is a C++ Program that Solves Number of Ways to Reach a Given Score Problem using Dynamic Programming technique.

Problem Description

In a game, a player can score only 3, 5 or 10 points in a move. Given a score S, find the number of ways to reach the given score using the specified moves.

Problem Solution

This problem can be solved using Dynamic Programming. The approach is to first calculate the number of ways to reach a smaller score using only move with 3 points. Store these values in an array. Then apply the procedure using move with 5 points and then finally with 10 points.

Time Complexity of this solution is O(score).

Expected Input and Output

Case-1:

 
Score=22
No. of ways=2    using 3+3+3+3+5+5, 3+3+3+3+10

Program/Source Code

Here is source code of the C++ Program to Solve Number of Ways to Reach a Given Score Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
using namespace std;
```
```
 
```
```
int countWays(int score)
```
```
{
```
```
    int i;
```
```
 
```

    //create an array to store the calculated results for smaller score

```
    int result[score+1];
```
```
 
```

    //result[i]=no. of ways to reach score i

```
 
```
```
    //initialization
```

    result[0]=1;   //since, there is only one way to reach NIL score is to don't make any move

```
 
```

    //initialize result[0]=0 for all other values

```
    for(i=1;i<=score;i++)
```
```
        result[i]=0;
```
```
 
```

    //First count the ways to reach the score i using only 3

```
    for(i=3;i<=score;i++)
```
```
        result[i]+=result[i-3];
```
```
 
```
```
    //Now, count the ways using move 5
```
```
    for(i=5;i<=score;i++)
```
```
        result[i]+=result[i-5];
```
```
 
```

    //now, the final result will be calculated

```
    for(i=10;i<=score;i++)
```
```
        result[i]+=result[i-10];
```
```
 
```
```
    return result[score];
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int score;
```
```
 
```
```
    cout<<"Enter the score"<<endl;
```
```
    cin>>score;
```
```
 
```

    cout<<"No. of ways to reach the given score are"<<endl;

```
    cout<<countWays(score);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the value score. We pass this value to the function countWays as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

Runtime Test Cases

 
Case-1:
$ g++ reach_score.cpp
$ ./a.out
Enter the score
22
No. of ways to reach the given score are
2

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Minimum Number of Jumps Problem – Dynamic Programming Solutions

» Next - Shortest Common Subsequence using Dynamic Programming

Related Posts:

Recommended Articles: