难以找到表示整数所需的最小1数。

Question

为了好玩，我做了一些编程上的挑战，我在一个关于如何仅用整数来表示整数的问题上陷入了困境。问题是，使用+、x和c操作来表示小于100000的整数所需的最小数目是多少，其中c是连接运算(12 12 34 = 1234)。这个值在问题定义中被称为复杂性C(n)。我的解决方案使用了一个备忘录数组，在这个数组中，我保留了我已经处理过的每个数字的复杂性。对于每一个新的整数，我从所有的因式分解、所有的级联和整数减1中取最小的复杂度来得到复杂度。例如，对于77的整数，我将复杂度赋值为min( C(7) + C(11 )，C(7) + C(7)，C(76) + C(1) )。我对此的推理是，由于级联、分解和减法都会导致较小的整数，所以这些部分的复杂度总是最小的。

对于10101和99999这样的整数，这个解决方案得到了正确的答案，但由于某种原因，它只能停留在99984上。我找到的解决办法是：

(( 1) C(1)C_(1)x (1+1+1) x (1+1+1) )(1+1)C_1)x (1+1+1+1) = 99984

这里的复杂性变成C(99984) = 16，这显然是错误的。在这个问题上，我一直视而不见，很想知道我哪里出了错。下面是我的Python 3代码：

def find_complexity(input_number):
    complexity_array = [0]*(input_number+1)
    complexity_array[1] = 1
    largest_divisor = 2

    for number in range(2, input_number+1):
        smallest_complexity = number
        
        #Loop through all concatenation splits
        str_number = str(number)
        for i in range(len(str_number)-1):
            tail = str_number[i+1:]
            if tail[0] == '0':
                continue
            head = str_number[:i+1]
            complexity_sum = complexity_array[int(head)] + complexity_array[int(tail)]
            if smallest_complexity > complexity_sum:
                smallest_complexity = complexity_sum
                
        #Loop through all factorizations
        if number == largest_divisor**2:
            largest_divisor += 1
        for divisor in range(2, largest_divisor):
            if number % divisor != 0: 
                continue
            dividend = number // divisor
            complexity_sum = complexity_array[dividend] + complexity_array[divisor]
            if smallest_complexity > complexity_sum:
                smallest_complexity = complexity_sum
                
        #Loop through all summations
        complexity_sum = complexity_array[number-1] + 1
        if smallest_complexity > complexity_sum:
            smallest_complexity = complexity_sum
        
        complexity_array[number] = smallest_complexity
    
    return complexity_array[input_number]

input_number = 99984
output = find_complexity(input_number)
print(output)

Answer 1

你忘了一些可能的手术。对于任何整数n，您可以通过k和n-k之和达到它，对于任何1 <= k <= n-1。

例如，考虑53。它可以编写为(1 © 1) + ((1 + 1) x ((1 + 1) © 1))，所以C(53) = 7，您的代码返回8。

注意，53是代码错误的第一个整数。

我认为您没有任何实现问题，所以我让您编写这个代码。