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


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.

  1. #include<iostream>
  2. using namespace std;
  4. int countWays(int score)
  5. {
  6.     int i;
  8.     //create an array to store the calculated results for smaller score
  9.     int result[score+1];
  11.     //result[i]=no. of ways to reach score i
  13.     //initialization
  14.     result[0]=1;   //since, there is only one way to reach NIL score is to don't make any move
  16.     //initialize result[0]=0 for all other values
  17.     for(i=1;i<=score;i++)
  18.         result[i]=0;
  20.     //First count the ways to reach the score i using only 3
  21.     for(i=3;i<=score;i++)
  22.         result[i]+=result[i-3];
  24.     //Now, count the ways using move 5
  25.     for(i=5;i<=score;i++)
  26.         result[i]+=result[i-5];
  28.     //now, the final result will be calculated
  29.     for(i=10;i<=score;i++)
  30.         result[i]+=result[i-10];
  32.     return result[score];
  33. }
  35. int main()
  36. {
  37.     int score;
  39.     cout<<"Enter the score"<<endl;
  40.     cin>>score;
  42.     cout<<"No. of ways to reach the given score are"<<endl;
  43.     cout<<countWays(score);
  45.     cout<<endl;
  46.     return 0;
  47. }
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.

Participate in Data Structure I Certification Contest of the Month Now!
Runtime Test Cases
$ g++ reach_score.cpp
$ ./a.out
Enter the score
No. of ways to reach the given score are

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


Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.