Учитывая замаскированное число, подсчитайте все возможные числа, делимые на n

Question

У меня есть упражнение по динамическому программированию, но я не знаю, как оно будет работать здесь:

У нас загадочным номером является строка, состоящая из цифр и звездочки *. Учитывая загадочное число, подсчитайте все возможные натуральные числа, чтобы заменить звездочку * цифрой, чтобы получить целое число, делимое на n. Для примера:

Для 1*1* и n = 6 существует 16 возможных чисел, делимых на n: 1014, 1110, 1116, 1212, 1218, 1314, 1410, 1416, 1512, 1518, 1614, 1710, 1716, 1812, 1818, 1914.

Если есть ведущая звездочка, то она никогда не должна заменяться на ноль:

* 12 -> 112 (все в порядке), но *12 -> 012 (не в порядке)

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

1 <= inputString.size <= 1000

1 <= n <= 1000

Лимит времени:

500 мс на языке C++. Как я уже сказал, это упражнение по динамическому программированию.

Кто-нибудь может дать мне несколько советов по этому поводу?

Answer 1

Я пишу JavaScript для вас, это работает, вы можете изменить его на C++, также оставить комментарий для вас. он использует рекурсив для обработки и замены каждого * слева и замены на возможные числа

var string = "пример числа мистерий"

function Func(mysNumber , n ) 
{
    // this function 
    var realnumber = true // a check if number is not mystrius anymore!!
    for (var i=0 ; i<= mysNumber.length ; i++)
    {
        if(i !=0 && mysNumber[i]=="*") // for  Not left number
        {
            realnumber= false
            for(var j=0 ; j<=9 ;j++ )
            {
                Func(mysNumber.substring(0,i) + j.toString() + mysNumber.substring(i+1,mysNumber.length) ,n)
            }
        }
        else if (mysNumber[i]=="*") // for left number 
        {
            realnumber = false
            for(var j=1 ; j<=9 ;j++ )
            {
                Func(mysNumber.substring(0,i) + j.toString() + mysNumber.substring(i+1,mysNumber.length) ,n)
            }

        }
    }

    if(realnumber)
        if(parseInt(mysNumber) % n ==0)
            print(mysNumber)


}
func(string , 6)