Сложность: 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).
😎 Решение:
public class Solution {
private int mod = 1_000_000_007;
private int Dfs(int[] dp, int start, string s, int k) {
if (dp[start] != 0) return dp[start];
if (start == s.Length) return 1;
if (s[start] == '0') return 0;
long count = 0;
for (int end = start; end < s.Length; ++end) {
string currNumber = s.Substring(start, end - start + 1);
if (long.Parse(currNumber) > k) break;
count = (count + Dfs(dp, end + 1, s, k)) % mod;
}
dp[start] = (int)count;
return (int)count;
}
public int NumberOfArrays(string s, int k) {
int[] dp = new int[s.Length + 1];
return Dfs(dp, 0, s, k);
}
}Ставь 👍 и забирай 📚 Базу знаний