Count Ways to Score in a Game

Explore how to calculate all possible ways to reach a total score in a game where points of 1, 2, or 4 can be scored each turn. Understand the transition from a naive recursive approach to optimized solutions using dynamic programming through memoization and tabulation methods. This lesson guides you to improve time and space efficiency while applying core recursive number patterns in dynamic programming.

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