gpt4 book ai didi

c++ - 内存解决方案提供 TLE,而表格解决方案则不提供

转载 作者:行者123 更新时间:2023-11-28 04:14:48 28 4
gpt4 key购买 nike

我正在尝试来自 Interviewbit 的以下问题:

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

NOTE: You can only move either down or right at any point in time.

我写了以下内存解决方案:

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。我到底哪里错了?

最佳答案

测试用例在网格中有负数(尽管它们明确提到了非负数)。所以 dp[i][j] 可以是负数,但你的函数永远不会考虑这些值。只是使用另一个 vector 来存储访问过的单元格,它被接受了。

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);
}

关于c++ - 内存解决方案提供 TLE,而表格解决方案则不提供,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56914845/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com