我正在 Hackerrank 上尝试这个挑战:https://www.hackerrank.com/challenges/the-power-sum/problem
有两种方法可以解决这个问题:
- 递归
- 动态规划
我的问题:我不明白递归解决方案的一部分。我不明白当它一直设置为零时它如何能够跟踪“答案”。
示例输入:
29
2
正确答案:2
示例输出:
cur 0
cur 0
cur 0
cur 0
the 0
cur 0
the 0
the 0
cur 0
cur 0
the 0
the 0
cur 0
the 0
cur 0
the 0
the 0
cur 0
cur 0
a match:
4 9 16 the 1
the 1
cur 0
the 1
a match:
4 25 the 2
the 2
cur 0
cur 0
the 0
the 2
cur 0
the 2
cur 0
the 2
代码:
import math
import os
import random
import re
import sys
def powerSum(x, n, value):
s = sum (v**n for v in value)
if s == x:
print "a match:"
for v in value:
print v**n,
return 1
else:
v = value[-1] + 1 if value else 1
answer = 0
print "cur", answer
while s + v**n <= x:
answer += powerSum(x, n, value+[v])
v += 1
print "the", answer
return answer
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
x = int(raw_input())
n = int(raw_input())
value = []
result = powerSum(x, n, value)
fptr.write(str(result) + '\n')
fptr.close()
请您参考如下方法:
您在问题中提供的代码以稍微复杂的方式实现了递归。就这些。考虑一下相同代码的不同版本:
def powerSum(x, n, value):
answer = 0
s = sum(v**n for v in value)
# base case
if s == x:
answer = 1
# recursive case
else:
v = value[-1] + 1 if value else 1
while s + v**n <= x:
answer += powerSum(x, n, value+[v])
v += 1
return answer
