python - SPOJ-代码-Python 3中的NZEC错误

我刚刚发现了SPOJ网站，并提交了我的第一个问题解决方案：Alphacodehttp://www.spoj.com/problems/ACODE/
在线法官以NZEC错误回答了下面的代码，我不明白为什么。我选择了Python3.2.3（Python3.2中出现了functools.lru缓存），我还尝试删除lru缓存并用memoize decorator替换它，但问题是一样的。

from functools import lru_cache

@lru_cache(maxsize=10000)
def acode(s, i=0):
    if i == len(s):
        return 1
    if s[i] == "0":
        return 0
    res = acode(s, i+1)
    if i + 1 < len(s) and (10 * int(s[i]) + int(s[i+1]) <= 26):
        res += acode(s, i+2)
    return res

def main():
    i = input().strip()
    while i != "0":
        print(acode(i))
        i = input().strip()

if __name__ == "__main__":
    import sys
    try:
        main()
    except:
        sys.exit(0)

可以使用以下命令对其进行测试：

$ echo "123\n1111\n21\n0" | python3 acode.py

注：我也提交了没有“尝试：除了：”但我找不到输出日志上的SPOJ网站。

最佳答案

你的程序似乎没有给NZEC（至少现在）。但是，它用WA密码来解决问题。
但是，如果我使用动态编程显式地回滚数组，而不是使用LRU缓存，那么它将被接受

from functools import lru_cache


@lru_cache(maxsize=10000)
def acode(s, i=0):
    if i == len(s):
        return 1
    if s[i] == "0":
        return 0
    res = acode(s, i + 1)
    if i + 1 < len(s) and (10 * int(s[i]) + int(s[i + 1]) ≤ 26):
        res += acode(s, i + 2)
    return res


def acode_second_try(s):
    n = len(s)
    f = [0 for i in range(1 + n)]
    f[n] = 1
    for i in range(n - 1, -1, -1):
        if s[i] != '0':
            f[i] = f[1 + i]
            if 1 + i < n:
                if 10 * int(s[i]) + int(s[1 + i]) ≤ 26:
                    f[i] += f[2 + i]
    return f[0]


def main():
    i = input().strip()
    while i[0] != '0':
        print(acode_second_try(i))
        #print(acode(i))
        i = input().strip()

if __name__ == "__main__":
    import sys

    try:
        main()
    except:
        sys.exit(0)

关于python - SPOJ-代码-Python 3中的NZEC错误，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15784421/