<p>编写的代码与原始JavaScript非常匹配</p>
<p>虽然JavaScript名称可以工作,但我对函数和变量名称进行了重构,使之与<a href="https://www.python.org/dev/peps/pep-0008/#function-and-variable-names" rel="nofollow noreferrer">Python style</a>一致,即:</p>
<ul>
<li>函数名应该是小写的,并根据需要用下划线分隔单词,以提高可读性</李>
<li>变量名遵循与函数名相同的约定</李>
</ul>
<p><strong>代码</strong></p>
<pre><code>def best_sum(target_sum, numbers):
if target_sum == 0: return []
if target_sum < 0: return None
shortest_combination = None
for num in numbers:
remainder = target_sum - num
remainder_combination = best_sum(remainder, numbers)
if remainder_combination != None:
combination = [*remainder_combination, num] # Python * equivalent to JavaSscript ...
if shortest_combination == None or len(combination) < len(shortest_combination):
shortest_combination = combination
return shortest_combination
</code></pre>
<p><strong>测试</strong></p>
<pre><code>print(bestSum(7, [3, 4, 7])) # Output: [7]
</code></pre>
<p><strong>使用记忆(即缓存)</strong></p>
<pre><code>def best_sum(target_sum, numbers, memo = None):
if memo is None:
memo = {0:[]}
if target_sum < 0:
return None
if target_sum in memo:
return memo[target_sum]
shortest_combination = None
for num in numbers:
remainder = target_sum - num
remainder_combination = best_sum(remainder, numbers, memo)
if remainder_combination != None:
combination = [*remainder_combination, num] # Python * equivalent to JavaSscript ...
if shortest_combination == None or len(combination) < len(shortest_combination):
shortest_combination = combination
memo[target_sum] = shortest_combination
return memo[target_sum]
print(best_sum(7, [3, 4, 7])) # Output: 7
# Following very slow on non-memoized version
print(best_sum(100,[10,1,25])) # Output: [25, 25, 25, 25]
</code></pre>