Почему временная сложность самого длинного возрастающего пути в матрице равна O (нм)? ⇐ C++

[Anonymous]

Мне трудно понять временную сложность решения следующей задачи LeetCode 329. Самый длинный возрастающий путь в матрице:

При условии m x n целочисленная матрица, возвращает длину самого длинного возрастающего пути в матрице.
Из каждой ячейки вы может двигаться в четырех направлениях: влево, вправо, вверх или вниз. Вы не можете перемещать по диагонали или перемещаться за пределы границы (т. е. перенос не допускается).

Мое решение использует DFS с запоминанием:

Код: Выделить всё

class Solution {
public:
vector dir = {{1,0}, {-1, 0}, {0, 1}, {0,-1}};

int longestIncreasingPath(vector& matrix) {
if(!matrix.size()){
return 0;
}
vector ans;
vector row(matrix[0].size(), 0);
vector cache(matrix.size(), row);
int longest = 0;
for(int idx = 0; idx < matrix.size(); idx++){
for(int idy =0; idy < matrix[0].size(); idy++){
int cand = longestIncreasingPathRec(matrix, cache, -1, idx, idy);
longest = max(cand, longest);
}
}

return longest;

}

int longestIncreasingPathRec(vector& matrix, vector& cache, int prevValue, int x, int y){

if(x < 0 || y < 0 || x >= matrix.size() || y >= matrix[0].size()){
return 0;
}

if(matrix[x][y] = matrix.size() || newY >= matrix[0].size()){
continue;
}

result = std::max(result, longestIncreasingPathRec(matrix, cache, matrix[x][y], newX, newY) + 1 );
}

cache[x][y] = result;
return result;
}
};

В редакционной статье LeetCode указано, что временная сложность для этого подхода равна O(mn), где m — этоматрица.size(), а n — это матрица[0].size() :

Временная сложность: O(mn). Каждая вершина/ячейка будет рассчитана один и только один раз, а каждое ребро будет посещено один и только один раз. Тогда общая временная сложность составит O(V+E). V — общее количество вершин, а E — общее количество ребер. В нашей задаче O(V)=O(mn), O(E)=O(4V)=O(mn).

Задача< /h2>
Я сомневаюсь в приведенном выше утверждении, поскольку для решения этой проблемы нам нужно рассматривать все ячейки как начальную позицию и выполнять цикл, как показано ниже:

Код: Выделить всё

for(int idx = 0; idx < matrix.size(); idx++){
for(int idy =0; idy < matrix[0].size(); idy++){
// WORK DONE IN longestIncreasingPathRec is definetly not O(1)
}
}

Цикл сам по себе равен O(mn), и работа, выполняемая в рекурсивном методе, мне не кажется O(1), и мне кажется, что в худшем случае должно быть O(mn) поэтому общая временная сложность может составлять O(mn)^2. Почему O(nm), а не O(mn)^2?
Что мне здесь не хватает? Как здесь определить правильную временную сложность?
LeetCode также говорит о «подходе № 1», который просто использует DFS без запоминания, и упоминается, что временная сложность равна O(2^ (m+n)):

Временная сложность: O(2^(m+n)). Поиск повторяется для каждого допустимого возрастающего пути. В худшем случае у нас может быть вызовов O(2^(m+n)).

Опять же, мне тоже трудно это понять. . Мне кажется, что без запоминания каждая ячейка в худшем случае может повторяться mn раз, и в каждой ячейке у нас есть 4 варианта выбора (вверх, вниз, влево, вправо), так почему же временная сложность получается как O(2^(m+) n))?
Примечание: я также разместил свой запрос на разъяснения на форуме LeetCode и просмотрел другие комментарии по этому вопросу. Я нашел много вопросов относительно временной сложности этих подходов, но почти не получил ответов. Там где были ответы, не разъяснили, что я ищу, поэтому решил разместить свой вопрос здесь.

Подробнее здесь: https://stackoverflow.com/questions/793 ... rix-is-onm