1class Solution:
2 def countNumberOfScoreCombinations(self, scores, score):
3 dp = [[0 for _ in range(len(scores))] for _ in range(score + 1)]
4 # return self.recursive(scores, score, 0, 0, dp)
5 # return self.topDown(scores, 0, 0, dp)
6 return self.bottomUp(scores, score, dp)
7
8 def recursive(self, scores, score, s, i):
9 if s == score: return 1
10 if i >= len(scores) or s > score: return 0
11 comb1, comb2 = 0, 0
12 if s + scores[i] <= score and i + 1 <= len(scores): comb1 += self.recursive(scores, score, s + scores[i], i + 1)
13 if i + 1 <= len(scores): comb2 += self.recursive(scores, score, s, i + 1)
14 return comb1 + comb2
15
16 def topDown(self, scores, s, i, dp):
17 if s == 0: return 1
18 if i >= len(scores) or s < 0: return 0
19 if dp[i][s] == 0:
20 if s + scores[i] >= 0 and i + 1 <= len(scores): dp[i][s] += self.topDown(scores, s + scores[i], i + 1, dp)
21 if i + 1 <= len(scores): dp[i][s] += self.topDown(scores, s, i + 1, dp)
22 return dp[i][s]
23
24 def bottomUp(self, scores, score, dp):
25 for i in range(len(scores)): dp[i][0] += 1
26 for s in range(1, score + 1):
27 if dp[0][0] % s == 0: dp[0][s] += 1
28
29 for i in range(1, len(scores)):
30 for s in range(1, score + 1):
31 dp[i][s] += dp[i - 1][s]
32 if s - scores[i] >= 0: dp[i][s] += dp[i][s - scores[i]]