Задача на динамическое программирование - Вася и конструктор чисел

У Васи есть любимый конструктор чисел. Он представляет из себя табличку длины N и неограниченный запас цифр от 0 до 9.

Для каждого числа Вася считает его крутость. Крутость — это сумма произведений всех пар соседних цифр в числе, но при этом числа, в которых рядом стоят две одинаковые цифры, всегда имеют крутость 0. Вася очень любит играть с конструктором, поэтому он износился, и в некоторых позициях застряли цифры. Вася хочет узнать, насколько максимальная крутость числа в изношенном конструкторе меньше крутости самого крутого числа в новом конструкторе, в котором нет застрявших цифр.

Входные данные:

В первой строке записано число 1≤N≤10^5. Во второй строке содержится S длины N, в которой на позиции i стоит ∗ если позиция свободна, и на неё можно ставить любую цифру, в противном случае на i-й позиции записана цифра от 0 до 9.

Выходные данные:

Выведите единственное целое число: разницу между крутостью самого крутого числа в новом конструкторе и конструкторе Васи.

Мой код:

n = int(input())
table = input()
if table.replace('*', '') == '':
    print(0)
else:
    table = table.split()
    maximum = 72 * (n - 1)
    masked = 0

    # Что тут?

    print(maximum - masked)

Это задача на динамическое программирование, но я не знаю, какой массив создать и какие в нём рекуррентные соотношения. Буду рад любой подсказке. Желательно сегодня :)

P.S. Способы решения не важны, главное - эффективность.