11.3. Красивые числа

11_3.py

n = int(input())

split_table = {}


def get_split_sum(a, start_index, end):
    l = end - start_index + 1
    if l <= 2:
        return 0

    if (start_index + 1, end) in split_table:
        sum1 = split_table[(start_index + 1, end)]
    else:
        sum1 = get_split_sum(a, start_index + 1, end)
    if (start_index + 2, end) in split_table:
        sum2 = split_table[(start_index + 2, end)]
    else:
        sum2 = get_split_sum(a, start_index + 2, end)

    split_table[(start_index, end)] = min(a[start_index] + a[start_index + 1] + sum1,
                                          a[start_index + 1] + a[start_index + 2] + sum2)

    return split_table[(start_index, end)]

digits = []
while n > 0:
    digits.append(n % 10)
    n //= 10

IN_EVEN = 0
IN_ODD = 1
state = IN_EVEN
i = 0
start = 0
split_sum = 0

while i < len(digits):
    is_even = (digits[i] % 2 == 0)

    if is_even:
        if state == IN_ODD:
            if i - start + 1 > 2:
                split_sum += get_split_sum(digits, start, i)

            start = i
            state = IN_EVEN
    else:
        if state == IN_EVEN:
            if i - start + 1 > 2:
                split_sum += get_split_sum(digits, start, i)
            start = i
            state = IN_ODD
    i += 1
if i - start > 2:
    split_sum += get_split_sum(digits, start, i - 1)

print(split_sum)