C++ 解法, 执行用时: 153ms, 内存消耗: 13912KB, 提交时间: 2022-05-18
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param mp int整型vector<vector<>>
* @return int整型
*/
int dnd(vector<vector<int> >& mp) {
// write code here
int row=mp.size();
if(row==0) return 0;
int col=mp[0].size();
vector<int> dp(col);
dp[col-1]=mp[row-1][col-1]>0?1:-mp[row-1][col-1]+1;
for(int i=col-2;i>=0;i--)
dp[i]=max(1,dp[i+1]-mp[row-1][i]);
for(int i=row-2;i>=0;i--)
{
dp[col-1]=max(1,dp[col-1]-mp[i][col-1]);
for(int j=col-2;j>=0;j--)
dp[j]=min(max(1,dp[j]-mp[i][j]),max(1,dp[j+1]-mp[i][j]));
}
return dp[0];
}
};
/*
int dnd(vector<vector<int> >& mp) {
// write code here
int row=mp.size();
if(row==0) return 0;
int col=mp[0].size();
vector<vector<int>> dp(row,vector<int>(col));
dp[row-1][col-1]=mp[row-1][col-1]>0?1:-mp[row-1][col-1]+1;
for(int i=row-2;i>=0;i--)
dp[i][col-1]=max(1,dp[i+1][col-1]-mp[i][col-1]);
for(int i=col-2;i>=0;i--)
dp[row-1][i]=max(1,dp[row-1][i+1]-mp[row-1][i]);
for(int i=row-2;i>=0;i--)
{
for(int j=col-2;j>=0;j--)
dp[i][j]=min(max(1,dp[i+1][j]-mp[i][j]),max(1,dp[i][j+1]-mp[i][j]));
}
return dp[0][0];
}
*/
C++ 解法, 执行用时: 157ms, 内存消耗: 13896KB, 提交时间: 2022-08-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param mp int整型vector<vector<>>
* @return int整型
*/
int dnd(vector<vector<int> >& mp) {
// write code here
int row=mp.size();
if(row==0)
return 0;
int col=mp[0].size();
vector<int> dp(col);
dp[col-1]=mp[row-1][col-1]>0?1:-mp[row-1][col-1]+1;
for(int i=col-2;i>=0;i--)
dp[i]=max(1,dp[i+1]-mp[row-1][i]);
for(int i=row-2;i>=0;i--)
{
dp[col-1]=max(1,dp[col-1]-mp[i][col-1]);\
for(int j=col-2;j>=0;j--)
dp[j]=min(max(1,dp[j]-mp[i][j]),max(1,dp[j+1]-mp[i][j]));
}
return dp[0];
}
};
C++ 解法, 执行用时: 158ms, 内存消耗: 17852KB, 提交时间: 2022-02-22
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @return int
*/
int dnd(vector<vector<int>> &mp) {
int n = mp.size() , m = mp[0].size();
vector<vector<int>> dp(n + 2, vector<int>(m + 2, 0));
for (int i = 0; i <= n + 1; ++i)
dp[i][m] = 1000000000;
for (int i = 0; i <= m + 1; ++i)
dp[n][i] = 1000000000;
dp[n][m-1] = 1;
dp[n][m-1] = 1;
for (int i = n-1; i >= 0; --i)
{
for (int j = m-1; j >= 0; --j)
{
dp[i][j] = min(dp[i + 1][j] - mp[i][j] <= 1 ? 1 : dp[i + 1][j] - mp[i][j],
dp[i][j + 1] - mp[i][j] <= 1 ? 1 : dp[i][j + 1] - mp[i][j]);
}
}
return dp[0][0];
}
};
C++ 解法, 执行用时: 159ms, 内存消耗: 13848KB, 提交时间: 2022-06-16
class Solution {
public:
int dnd(vector<vector<int> >& mp) {
int a = mp.size();
if (a == 0)
return 0;
int b = mp[0].size();
vector<int> x(b);
x[b - 1] = mp[a - 1][b - 1] > 0 ? 1 : -mp[a - 1][b - 1] + 1;
for (int i = b - 2; i >= 0; i--)
x[i] = max(1, x[i + 1] - mp[a - 1][i]);
for (int i = a - 2; i >= 0; i--) {
x[b - 1] = max(1, x[b - 1] - mp[i][b - 1]);
for (int j = b - 2; j >= 0; j--)
x[j] = min(max(1, x[j] - mp[i][j]), max(1, x[j + 1] - mp[i][j]));
}
return x[0];
}
};
C++ 解法, 执行用时: 159ms, 内存消耗: 17796KB, 提交时间: 2022-03-29
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @return int
*/
int dnd(vector<vector<int>> &mp) {
int n = mp.size() , m = mp[0].size();
vector<vector<int>> dp(n + 2, vector<int>(m + 2, 0));
for (int i = 0; i <= n + 1; ++i)
dp[i][m] = 1000000000;
for (int i = 0; i <= m + 1; ++i)
dp[n][i] = 1000000000;
dp[n][m-1] = 1;
dp[n][m-1] = 1;
for (int i = n-1; i >= 0; --i)
{
for (int j = m-1; j >= 0; --j)
{
dp[i][j] = min(dp[i + 1][j] - mp[i][j] <= 1 ? 1 : dp[i + 1][j] - mp[i][j],
dp[i][j + 1] - mp[i][j] <= 1 ? 1 : dp[i][j + 1] - mp[i][j]);
}
}
return dp[0][0];
}
};
，矩阵中的值满足 