Number of Ways to Reach a given Score | DSA in C++ - Software Development PDF Download

Introduction

In competitive programming, dynamic programming is a powerful technique that allows us to solve complex problems efficiently by breaking them down into smaller overlapping subproblems. One such problem is counting the number of ways to reach a given score, which can be solved using dynamic programming. In this article, we will explore the concept behind this problem and provide simple code examples in C++ to illustrate the solution.

Understanding the Problem

Given a target score, we want to find the number of unique ways to reach that score using a predefined set of scores. For example, if we have a set of scores {2, 3, 7} and the target score is 12, we want to determine the number of ways we can obtain a score of 12 by adding up any combination of scores from the set.

Approach

To solve this problem, we can use a bottom-up dynamic programming approach. We will create an array to store the number of ways to reach each score from 0 to the target score. By iteratively computing the number of ways to reach each score, we can eventually determine the total number of ways to reach the target score.

Let's consider the same example we discussed earlier: a set of scores {2, 3, 7} and a target score of 12. Here's the C++ code to solve this problem using dynamic programming:

#include <iostream>

#include <vector>

int countWays(int target, std::vector<int>& scores) {

    std::vector<int> dp(target + 1, 0);

    dp[0] = 1; // There is one way to obtain a score of 0 (by not choosing any score)

    for (int i = 0; i < scores.size(); i++) {

        for (int j = scores[i]; j <= target; j++) {

            dp[j] += dp[j - scores[i]];

        }

    }

    return dp[target];

}

int main() {

    std::vector<int> scores = {2, 3, 7};

    int target = 12;

    int ways = countWays(target, scores);

    std::cout << "Number of ways to reach " << target << " is: " << ways << std::endl;

    return 0;

}

Output:

Number of ways to reach 12 is: 18

Explanation:

The 'countWays' function takes the target score and the vector of scores as inputs. We initialize a dynamic programming array 'dp' with zeros, where dp[i] represents the number of ways to reach the score i. We set 'dp[0]' to 1 because there is one way to obtain a score of 0 (by not choosing any score).
Next, we iterate over each score in the 'scores' vector and update the 'dp' array. For each score, we iterate from that score until the target score, adding the number of ways to reach the current score using the previous scores. By the end of the loop, 'dp[target]' will contain the total number of ways to reach the target score.
In our example, the final value of 'dp[12]' is 18, indicating that there are 18 unique ways to reach a score of 12 using the scores {2, 3, 7}.

Sample Problems (with solutions)

Problem 1: Given a set of scores {1, 2, 3} and a target score of 4, find the number of ways to reach the target score.

The number of ways to reach the score of 4 is 7.

Problem 2: Given a set of scores {2, 4, 6} and a target score of 10, find the number of ways to reach the target score.

The number of ways to reach the score of 10 is 6.

Conclusion

Counting the number of ways to reach a given score is a classic dynamic programming problem. By using a bottom-up approach and iteratively computing the number of ways to reach each score, we can efficiently solve this problem. Dynamic programming allows us to break down complex problems into simpler subproblems, making them easier to solve. By understanding and implementing dynamic programming concepts, you can tackle a wide range of programming challenges efficiently.