Varaint 1 of 16.1

#1

Elements of programming Interviews - Java

Problem 16.1- Count the number of score combinations

Variant 1 - Solve the same problem using O(s) space

How do you reduce space of the Cache? Any Ideas?

0 Likes
#2

Examine the way you use the contents of the cache in your code. At each step, when computing the cache, do you really need ALL the previous rows and columns? Is there some way to limit what’s kept in the cache to just what’s needed?

0 Likes
#3

lgout, are you sure it is O(s) but not O(n) space? If yes, can you provide more details, please?

0 Likes
#4

It can be done with O(s) space. Here is my attempt in python:

def num_combinations_for_final_score(final_score: int,
                                     individual_play_scores: List[int]) -> int:

    num_combinations_for_final_score = [1] + [0] * final_score
    for i in range(len(individual_play_scores)):
        for j in range(1, final_score + 1):
            without_play = num_combinations_for_final_score[j]
            with_play = num_combinations_for_final_score[j - individual_play_scores[i]] if j >= individual_play_scores[i] else 0
            num_combinations_for_final_score[j] = without_play + with_play
    return num_combinations_for_final_score[-1]
0 Likes