Memoized решение дает TLE, в то время как табличное решение не - PullRequest
Новая
       36

Memoized решение дает TLE, в то время как табличное решение не

0 голосов
/ 06 июля 2019

Я пытаюсь ответить на следующий вопрос из интервью:

Учитывая, что сетка amxn заполнена неотрицательными числами, найдите путь сверху вниз слева направо, который минимизирует сумму всех чисел на своем пути.

ПРИМЕЧАНИЕ. В любой момент времени вы можете двигаться только вниз или вправо.

Я написал следующее запомненное решение: 

int minPath(vector<vector<int> > &A, int i, int j, vector<vector<int> > &dp) {
if (dp[i][j] >= 0)
    return dp[i][j];
else if (i == A.size() - 1 && j == A[0].size() - 1)
    return dp[i][j] = A[i][j];
else if (i == A.size() - 1)
    return dp[i][j] = A[i][j] + minPath(A, i, j + 1, dp);
else if (j == A[0].size() - 1)
    return dp[i][j] = A[i][j] + minPath(A, i + 1, j, dp);
else
    return dp[i][j] = A[i][j] + min(minPath(A, i + 1, j, dp), minPath(A, i, j + 1, dp));
}

int Solution::minPathSum(vector<vector<int> > &A) {
if (A.size() == 0)
    return 0;

vector<vector<int> > dp(A.size(), vector<int>(A[0].size(), -1));
return minPath(A, 0, 0, dp);
}

ЭтоРешение заключается в предоставлении TLE во время представления.

Через некоторое время я взглянул на код редакции, и они следовали принципу табулирования следующим образом: 

int minPathSum(vector<vector<int> > &grid) {
        if (grid.size() == 0) return 0;
        int m = grid.size(), n = grid[0].size();
        int minPath[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            minPath[i][0] = grid[i][0]; 
            if (i > 0) minPath[i][0] += minPath[i - 1][0];
            for (int j = 1; j < n; j++) {
                minPath[i][j] = grid[i][j] + minPath[i][j-1];
                if (i > 0) minPath[i][j] = min(minPath[i][j], grid[i][j] + minPath[i-1][j]);
            }
        }
    return minPath[m-1][n-1];
}

По моему мнению,временная сложность обоих кодов кажется одинаковой, но моя, похоже, дает TLE.Где именно я иду не так?

1 Ответ

1 голос
/ 09 июля 2019

Тестовые случаи имеют отрицательные числа в сетке (хотя они явно упоминали неотрицательные числа).Таким образом, dp [i] [j] может быть отрицательным, но ваша функция никогда не будет учитывать эти значения.Просто использовал другой вектор для хранения посещенной ячейки, и он был принят. 

int minPath(vector<vector<int> > &A, int i, int j, vector<vector<int> > &dp,vector<vector<bool> > &vis)
{
    if (vis[i][j])
        return dp[i][j];
    vis[i][j] = 1;
    if (i == A.size() - 1 && j == A[0].size() - 1)
        return dp[i][j] = A[i][j];
    else if (i == A.size() - 1)
        return dp[i][j] = A[i][j] + minPath(A, i, j + 1, dp, vis);
    else if (j == A[0].size() - 1)
        return dp[i][j] = A[i][j] + minPath(A, i + 1, j, dp, vis);
    else
        return dp[i][j] = A[i][j] + min(minPath(A, i + 1, j, dp, vis), minPath(A, i, j + 1, dp, vis));
}

int Solution::minPathSum(vector<vector<int> > &A)
{
    if (A.size() == 0)
        return 0;

    vector<vector<int> > dp(A.size(), vector<int>(A[0].size(), -1));
    vector<vector<bool> > vis(A.size(), vector<bool>(A[0].size(), 0));
    return minPath(A, 0, 0, dp, vis);
}
...