algorithm - Alyona 和 Copybooks : what's wrong with this code

Question

这是来自 CodeForces # 381 (Div. 2) ( link ) 的 Alyona 和 Copybooks 的问题陈述。

Little girl Alyona is in a shop to buy some copybooks for school. She study four subjects so she wants to have equal number of copybooks for each of the subjects. There are three types of copybook's packs in the shop: it is possible to buy one copybook for a rubles, a pack of two copybooks for b rubles, and a pack of three copybooks for c rubles. Alyona already has n copybooks.

What is the minimum amount of rubles she should pay to buy such number of copybooks k that n + k is divisible by 4? There are infinitely many packs of any type in the shop. Alyona can buy packs of different type in the same purchase.

Input The only line contains 4 integers n, a, b, c (1 ≤ n, a, b, c ≤ 109).

Output Print the minimum amount of rubles she should pay to buy such number of copybooks k that n + k is divisible by 4.

我最初试图通过探索如何使教科书数量被 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

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

Answer 1

您的递归解决方案实际上是一个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()