Задача: 902. Numbers At Most N Given Digit Set
Сложность: hard

Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.

Пример:

Input: digits = ["1","3","5","7"], n = 100
Output: 20

👨‍💻 Алгоритм:

1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре.

2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n.

3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел.

😎 Решение:

function atMostNGivenDigitSet($digits, $n) {
    $s = strval($n);
    $K = strlen($s);
    $dp = array_fill(0, $K + 1, 0);
    $dp[$K] = 1;

    for ($i = $K - 1; $i >= 0; --$i) {
        foreach ($digits as $d) {
            if ($d < $s[$i]) {
                $dp[$i] += pow(count($digits), $K - $i - 1);
            } elseif ($d == $s[$i]) {
                $dp[$i] += $dp[$i + 1];
            }
        }
    }

    for ($i = 1; $i < $K; ++$i) {
        $dp[0] += pow(count($digits), $i);
    }

    return $dp[0];
}

Ставь 👍 и забирай 📚 Базу знаний