Понимание тайм-аутов динамического программирования с помощью двух разных решений
Проблема в литкоде (ссылка — https://leetcode.com/problems/the-number-of-ways-to-make-the-sum/description/)
У вас есть бесконечное количество монет номиналом 1, 2 и 6 и только 2 монеты номиналом 4.
Учитывая целое число n, выведите количество способов составить сумму n с имеющимися у вас монетами.
Поскольку ответ может быть очень большим, верните его по модулю 109 + 7.
Обратите внимание, что порядок монет не имеет значения и [2, 2, 3] совпадает с [2, 3, 2].
Пример 1:
Вход: n = 4
Выход: 4
Объяснение:
Вот четыре комбинации: [1, 1, 1, 1], [1, 1, 2], [2, 2], [4].
Ограничения 1 <= п <= 10^5
Хотя я написал решение как
vector<int> temp{1,2,6};
class Solution {
public:
long long getTotalNumberOfWays(int n,int index,vector<vector<long long>>& dp){
if (n==0){
return 1;
}
if (n<0 || index>2){
return 0;
}
if (dp[index][n]!=-1){
return dp[index][n];
}
long long totalWaysWithoutFour = 0;
int newN = n;
while(newN>=0){
totalWaysWithoutFour += getTotalNumberOfWays(newN,index+1,dp);
newN-=temp[index];
}
return dp[index][n] = totalWaysWithoutFour;
}
int numberOfWays(int n) {
vector<vector<long long>> dp(3,vector<long long>(n+1,-1));
return (int)(getTotalNumberOfWays(n,0,dp) + getTotalNumberOfWays(n-4,0,dp) + getTotalNumberOfWays(n-8,0,dp))%((long long)pow(10,9)+7);
}
};
Я получаю тайм-аут в приведенном выше коде. Хотя если я сделаю это
vector<int> temp{1,2,6};
class Solution {
public:
long long getTotalNumberOfWays(int n,int index,vector<vector<long long>>& dp){
if (n==0){
return 1;
}
if (n<0 || index>2){
return 0;
}
if (dp[index][n]!=-1){
return dp[index][n];
}
long long totalWaysWithoutFour = 0;
return dp[index][n] = ((getTotalNumberOfWays(n-temp[index],index,dp)) + (getTotalNumberOfWays(n,index+1,dp)));
}
int numberOfWays(int n) {
vector<vector<long long>> dp(3,vector<long long>(n+1,-1));
return (getTotalNumberOfWays(n,0,dp) + getTotalNumberOfWays(n-4,0,dp) + getTotalNumberOfWays(n-8,0,dp))%((long long)(pow(10,9)+7));
}
};
Код проходит нормально. Насколько я понимаю, первый и второй код имеют одинаковую временную сложность. Я ошибаюсь в этом предположении, если нет, то почему время ожидания первого истекло.
@user24714692 user24714692, извини, обновил второй код.
@Unmitigated 1 <= n <= 10^5 . В основном я хотел понять, почему 1-е и 2-е решения будут иметь разную временную сложность.
Как вы думаете, почему они имеют одинаковую сложность? В первом есть while(newN>=0)-цикл, который, скорее всего, имеет другую сложность, чем два рекурсивных вызова во втором алгоритме. Конечно, чтобы быть уверенным, это необходимо проанализировать дальше.
Ответы 2
Первая программа имеет квадратичное время выполнения, тогда как вторая программа имеет линейное время выполнения.
Абстрактно, ваша первая программа вычисляет это:
U(n, index) = sum(U(n-coin*i, index+1) for i=0...n/coin[index])
И ваша вторая программа вычисляет это:
V(n, index) = V(n, index+1) + V(n-coin[index], index)
и оба кэшируют предыдущие результаты и правильно обрабатывают крайние случаи.
В вашей первой программе (которую я назвал U) для вычисления любой записи в таблице dp требуется время Theta(n/coin), даже если все необходимые результаты уже вычислены. Таким образом, даже для одной монеты номиналом 1 первая программа является квадратичной.
В вашей второй программе этой ошибки нет — время O(1) при условии, что предыдущие результаты кэшируются.
Поскольку все элементы dp в конечном итоге будут вычисляться ровно один раз, это означает, что ваша первая программа будет Theta(N²*coins), а вторая — Theta(N*coins).
Кроме того, я мог бы написать то, что вы назвали getTotalNumberOfWays, вот так, без рекурсии и без зависимостей от глобальных переменных, а также с включением mod, чтобы избежать переполнения для более крупных n:
int getTotalNumberOfWays(int n, int mod, std::vector<int>& coins) {
if (n < 0) {
return 0;
}
std::vector<int> T(n + 1);
T[0] = 1;
for (int c : coins) {
for (int i = c; i <= n; ++i) T[i] = (T[i - c] + T[i]) % mod;
}
return T[n];
}
(это зависит от 2*mod <= INT_MAX).
При итеративном решении цикл можно полностью перенести в метод numberOfWays, чтобы вычислять таблицу только один раз.
Я понимаю, что это не совсем ответ на вопрос, но, кажется, стоит отметить, что, поскольку нам нужно только подсчитать решения, а не перечислить их, это можно решить за постоянное время O (1), просто используя некоторые арифметические действия.
Очевидно, что если бы у нас были только 1, единственным решением было бы использовать n1.
Введите 2с. У нас есть базовое решение со всеми 2 (плюс один 1, если n нечетное). Тогда мы можем разложить ноль или более 2 в пары 1, так что у нас будет ровно n / 2 + 1 решений.
Теперь о 6с. Опять же, у нас есть базовое решение со всеми 6 (плюс несколько 2 или 1, если n не кратно шести, но давайте пока забудем об этом). И снова мы можем разложить ноль или более 6 в тройки 2, которые, в свою очередь, можно разложить в 1, как мы уже видели. Когда мы расширяем ноль 6, у нас есть одно решение, когда мы расширяем единицу, у нас есть четыре решения (потому что три 2 дают четыре решения) и так далее. Ряд выглядит как 1, 4, 7, 10, ..., и мы должны просуммировать эти значения, чтобы получить 1, 5, 12, 22, .... Это известная последовательность, которую можно сгенерировать с помощью 3 * i * (i + 1) / 2 + i + 1, поэтому мы просто присваиваем i = n / 6 количество решений для n, когда n кратно шести.
Нам еще предстоит разобраться с остатком r = n % 6, если n не кратно шести. Если r один, ничего не меняется. Если их два или три, нам придется добавить по одному решению для каждого возможного числа разложений 6 (потому что, например, при одном разложении у нас было три 2 и, следовательно, четыре решения, но теперь у нас есть четыре 2, итак пять решений); если их четыре или пять, мы добавим по два решения для каждого расширения. Итак, мы должны добавить r / 2 * (i + 1) к нашему предыдущему результату.
Давайте просуммируем значения, которые мы получаем для n, n - 4 и n - 8, когда это необходимо, чтобы обработать 4, и все готово.
Оба имеют одинаковый код?