Count Ways to Score in a Game

Explore how to calculate the number of ways to achieve a total game score using points of 1, 2, or 4. Understand both naive recursive and optimized dynamic programming solutions with memoization and tabulation. This lesson helps you apply DP patterns to improve time complexity and efficiently solve scoring problems.

We'll cover the following...

Statement
Examples
Try it yourself
Solution
- Naive approach
  - Time complexity
  - Space complexity
- Optimized solution using dynamic programming
  - Top-down solution
    - Time complexity
    - Space complexity
  - Bottom-up solution
    - Time complexity
    - Space complexity

Statement

Suppose there is a game where a player can score either $1$ , $2$ , or $4$ points in each turn. Given a total score, $n$ , find all the possible ways in which you can score these $n$ points.

Note: You may assume that you can use a specific score as many times as you want. Additionally, the order in which we select scores from the list is significant.

Let's say the total points to be earned are $3$ . A player can score this total in the following three ways:

$1, 1$ and $1$ , in three turns: $1+1+1 = 3$ .
$1$ and then a $2$ , in two turns: $1 + 2 = 3$ .
$2$ and then a $1$ , in two turns: $2 + 1 = 3$ ...

1.Getting Started

2.0/1 Knapsack

3.Unbounded Knapsack

4.Recursive Numbers

5.Longest Common Substring

6.Palindromic Subsequence

7.Conclusion

Count Ways to Score in a Game

Statement