This is a C++ Program that Solves Number of Ways to Reach a Given Score Problem using Dynamic Programming technique.
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.
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).
Score=22 No. of ways=2 using 3+3+3+3+5+5, 3+3+3+3+10
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.
using namespace std;
int countWays(int score)
//create an array to store the calculated results for smaller score
//result[i]=no. of ways to reach score i
result=1; //since, there is only one way to reach NIL score is to don't make any move
//initialize result=0 for all other values
//First count the ways to reach the score i using only 3
//Now, count the ways using move 5
//now, the final result will be calculated
cout<<"Enter the score"<<endl;
cout<<"No. of ways to reach the given score are"<<endl;
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.
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.