Задача: 1416. Restore The Array
Сложность: hard

Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей.

Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

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

1⃣Создать массив dp размера m + 1, чтобы хранить значения dfs(x).

2⃣Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе:
Если s[start] == 0, вернуть 0.
Если start = m, вернуть 1.
Инициализировать count = 0, чтобы считать количество возможных массивов.
Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1).
Обновить dp[start] значением dfs(start).

3⃣Вернуть dfs(0).

😎 Решение:

var Solution = function() {
    this.mod = 1_000_000_007;
};

Solution.prototype.dfs = function(dp, start, s, k) {
    if (dp[start] !== 0) return dp[start];
    if (start === s.length) return 1;
    if (s[start] === '0') return 0;

    let count = 0;
    for (let end = start; end < s.length; end++) {
        let currNumber = parseInt(s.slice(start, end + 1));
        if (currNumber > k) break;
        count = (count + this.dfs(dp, end + 1, s, k)) % this.mod;
    }

    dp[start] = count;
    return count;
};

Solution.prototype.numberOfArrays = function(s, k) {
    let dp = Array(s.length + 1).fill(0);
    return this.dfs(dp, 0, s, k);
};

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