algorithm - 如何根据给定的规则（以DP的方式）找到最大的数字？

Question

问题：给定一个S格式为abcdefijak...的数字，每个字母代表一个数字。每 3 位数字组成一个 3 位素数，彼此不同。最大的可能是S什么？

有很多方法可以解决问题。我的问题是：如何在 DP 中解决它？

Answer 1

我写了一个愚蠢的蛮力算法：

def isprime(n):
    for x in xrange(2, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True

primes3 = filter(isprime, range(100, 1000))

def biggest():
    return max([biggie(x, set(primes3)-set([x])) for x in primes3])

def biggie(sofar, primes):
    next2 = sofar % 100
    found = sofar
    for prime in filter(lambda x: 10*next2 <= x < 10*(next2+1), primes):
        found = max(found, biggie(10*sofar + (prime % 10), primes - set([prime])))
    return found

这给了我的结果9419919379773971911373313179。谷歌搜索，发现：https ://stackoverflow.com/questions/3836008/find-largest-number-with-all-contiguous-triples-being-unique-primes

关闭为重复...

Answer 2

找出所有 3 位数的素数，并按降序依次排列。如果您的任务中没有未看到的需求，仅此而已。