algorithm - Alyona和Copybooks:这段代码有什么问题

这是来自codeforces 381（第2部分）的alyona和copybooks的问题声明（link）。
小女孩艾莉娜在一家商店里为学校买一些文案。她
学习四门课程，这样她就想有同等数量的文案
每一个主题。在
商店：一卢布一本，两本一包。
b卢布和c卢布的一包三本。
alyona已经有n本抄本了。
她买这个号码最少要付多少卢布
n + k可以被4整除有无限多
商店里任何类型的包装。Alyona可以购买不同类型的包装
在同一次购买中。
输入唯一一行包含4个整数n，a，b，c
（1≤N，A，B，C≤109）。
输出打印她应该支付的最低金额的卢布
n + k可被4整除的文案k的数目。
我最初试图通过探索所有的可能性来解决这个问题，即如何使教科书的数量可以被4整除。设f（n）为购买x本教科书的最小成本，使（n+x）%4=0。然后，f(n)=min(f(n+1)+a, f(n+2)+b, f(n+3)+c)。完整代码如下：

import sys
INF = sys.maxsize

def solution(n, prices):
    if n % 4 == 0:
        return 0
    else:
        ans = INF
        ans = min(solution(n + 1, prices) + prices[A],
              solution(n + 2, prices) + prices[B],
              solution(n + 3, prices) + prices[C])
        return ans

但是，它并没有通过所有的测试用例。我不知道为什么。这种方法有什么问题？

最佳答案

您的递归解决方案实际上是一个3-way递归树。
调用solution(3)时，每个步骤的调用堆栈为：
[sol(4),sol(5),sol(6)]>[sol(5),sol(6)]>[sol(6),sol(7),sol(8),sol(6)]>[sol(7),sol(8),sol(9),sol(7),sol(8),sol(6)]>>……
这会产生内存问题，如超出堆栈限制请从此处删除递归您可以将解决方案修改为：

def solution(n,prices):
  if n%4==0:
    return 0
  rem = 4-(n%4)
  if rem==1:
    return min(prices[0],prices[1]+prices[2],3*prices[2])
  elif rem==2:
    return min(2*prices[0], prices[1], 2*prices[2])
  else:
    return min(3*prices[0],prices[0]+prices[1],prices[2])

希望有帮助！！！
编辑：我修改了你的递归解决方案来终止无休止的递归。

import sys
INF = sys.maxsize

def solution(n, prices, k):
    if k>10:
        return INF
    if n % 4 == 0:
        return 0
    else:
        ans = min(solution(n + 1, prices,k+1) + prices[0],
              solution(n + 2, prices,k+2) + prices[1],
              solution(n + 3, prices,k+3) + prices[2])
        return ans

def main():
  n,a,b,c = map(int, raw_input().split())
  prices = [a,b,c]
  print solution(n,prices,0)

main()

关于algorithm - Alyona和Copybooks:这段代码有什么问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40798216/