solved task for sum of 3 sequent digit are not greater than 9

solved_2018_20.py

answer_20 = 378158756814587

def is_num_right(num):
    if num < 100:
        return sum(map(int, str(num))) <= 9

    for i in range(len(str(num)) - 2):
        if sum(map(int, str(num)[i:i+3])) > 9:
            return False
    return True

def brute_force_calc(digit_amount):
    result = []
    for k in range(10**(digit_amount - 1), 10**(digit_amount)):
        if is_num_right(k):
            result.append(k)
    return result

def get_ans_for_len_and_ending(l, ending):
    count = 0
    for k in brute_force_calc(l):
        if k % 100 == ending:
            count += 1

    return count

# Проверим, что a может быть получена из b путём добавления цифры d
def can_be_a_triple(a, b, d):
    return a == (b * 10 + d) % 100 and is_num_right(b * 10 + d)

dp = [[0 for j in range(100)] for i in range(21)]

for i in range(100):
    dp[3][i] = get_ans_for_len_and_ending(3, i)   
 
    
for i in range(4, 21):
    for j in range(100):
        for ending in range(100):
            # Не забываем проверять на правильность окончаний как таковых
            # Потому что из неверного окончания (19, например) можно получить верное (к 19 добавить цирфу 0 и получится 90 - верное)
            if not (is_num_right(j) and is_num_right(ending)):
                continue

            for d in range(10):
                if can_be_a_triple(j, ending, d):
                    dp[i][j] += dp[i - 1][ending]


print(sum([dp[20][i] for i in range(100)]) == answer_20)