algorithm - 采访 - 甲骨文

Question

在一场比赛中，唯一可以得分的是 2、3、4、5、6、7、8，并且可以得分任意次数

该队能打出的组合总数是多少，能达到50分的分数。

示例 8,8,8,8,8,8,2 有效 8,8,8,8,8,4,4,2 也有效。等等……

Answer 1

这个问题可以用动态规划来解决，有2个参数:

• i - 我们考虑到的索引
• s - 总分。

f(i, s) 将包含获得分数 s 的方法总数。

令 score[] 成为可获得的唯一正面分数的列表。

DP 解决方案的公式:

f(0, s) = 1, for all s divisible to score[0]
f(0, s) = 0, otherwise

f(i + 1, s) = Sum [for k = 0 .. floor(s/score[i + 1])] f(i, s - score[i + 1] * k)