Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Find Combinations for Game Scoring

Explore techniques to solve dynamic programming problems by finding all the combinations to reach a given game score using scoring increments of 1, 2, or 4 runs. Understand recursive solutions, optimize with memoization, and apply tabulation for efficient computation and reduced complexity.

We'll cover the following...

Statement

Imagine a game where, in each turn, a player can score either 1,21, 2 or 44 runs. Given a score, n, find the total number of ways to score n runs.

Examples

To score 33 runs, a player can score in the following three ways:

g n n = 3 array 1 1 1 1 2 2 1

To score 55 runs, a player can score in the following ten ways:

g n n = 5 array 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 1 1 2 2 1 4 2 1 1 1 2 1 2 2 2 1 4 1

Sample input

5

Expected output

10

Try it yourself

#include <iostream>

#include <vector>

using namespace std;



// Scoring options are 1, 2, and 4

int ScoringOptions(int n) {

	// TODO: Write - Your - Code

	return -1;

}

Solution 1: Recursion

We can only score 11, 22, or 44 points in this game. To reach a score of nn, we can only use increments of 11, 22, or 44. To reach a score of n+1n + 1, we can:

  • score 11 in the last turn
  • score
...