我刚刚在一次采访中被问到这个问题。
问题是:
我有一个矩阵如下:
3 3
0 1 -1
1 0 -1
1 1 1
第一行包含
row numbers (n)
和column numbers (m)
下面是给定的矩阵,其中1
表示金币,-1
表示障碍物。规则:
我必须从
(0, 0)
转到(n-1, m-1)
然后再从(n-1, m-1)
转到(0, 0)
返回。从
right
转到down
时,我只能移动到(0, 0)
和(n-1, m-1)
,从left
返回up
时,我只能移动到(n-1, m-1)
和(0, 0)
。在上面的旅行中,如果我遇到一个
1
,我就会捡起那块金子。类似地,当我在回来的路上遇到一个1
时,我会发现这个1
。如果
(n-1, m-1)
值为“cc>”或“无cc~>”,则整体金块数为0。问题是找到可以积累的黄金碎片的最大数量。
我的方法:
在采访期间,我推断规则推断如果我们将
-1
到(n-1, m-1)
的规则和(0, 0)
到(n-1, m-1)
的规则合并在一起,我们将基本上想要达到(n-1, m-1)
到(0, 0)
的所有可能方向:上、右、下和左我所要做的是在使用这4个路径的方向上计算最大数1。然后我提出了下面的递归代码,它看起来效率不高,但可以工作。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int mat[100][100];
int lookup[100][100];
int getcount(int pgc, int r, int c) {
if(r == n-1 && c == m-1) {
if(mat[r][c] == -1) return 0;
else return mat[r][c] + pgc;
}
int cgc = mat[r][c];
int tmp1 = 0, tmp2 = 0, tmp3 = 0, tmp4 = 0;
if (((r + 1) < n) &&( mat[r + 1][c] != -1) && (lookup[r+1][c] != -1)) {
// go down
lookup[r + 1][c] = -1;
tmp1 = getcount(cgc + pgc, r + 1, c);
lookup[r + 1][c] = 0;
}
if (c + 1 < m && mat[r][c + 1] != -1 && lookup[r][c+1] != -1) {
// go right
lookup[r][c + 1] = -1;
tmp2 = getcount(cgc + pgc, r, c + 1);
lookup[r][c + 1] = 0;
}
if (r - 1 >= 0 && mat[r - 1][c] != -1 && lookup[r - 1][c] != -1) {
// go up
lookup[r - 1][c] = -1;
tmp3 = getcount(cgc + pgc, r - 1, c);
lookup[r - 1][c] = 0;
}
if (c - 1 >= 0 && mat[r][c - 1] != -1 && lookup[r][c-1] != -1) {
// go left
lookup[r][c - 1] = -1;
tmp4 = getcount(cgc + pgc, r, c - 1);
lookup[r][c - 1] = 0;
}
return max(tmp1, max(tmp2, max(tmp3, tmp4)));
}
int collectMax() {
int ans = 0;
if(mat[n-1][m-1] == -1 || mat[0][0] == -1) ans = 0;
else {
int r = 0, c = 0;
int gc = 0;
// if(mat[0][0] == 1) gc = 1;
ans = getcount(gc, r, c);
ans = max(0, ans);
}
return ans;
}
int main() {
cin>>n>>m;
for(int i = 0; i<n; i++) {
for(int j = 0; j<m; j++) {
cin>>mat[i][j];
}
}
cout<<collectMax()<<endl;
return 0;
}
如何提高效率是否有使用dp优化的范围?
一些用于实践的示例测试用例:
输入1:
3 3
0 1 -1
1 0 -1
1 1 1
输出1:
5
输入2:
3 3
0 1 1
1 0 1
1 1 1
输出2:
7
输入3:
3 3
0 1 1
1 0 -1
1 1 -1
输出3:
0
最佳答案
这有一个在O(min(m2n,mn2))时间和O(min(m2,n2))空间使用动态规划的解决方案。
我们的想法是考虑像这样的有角度的“条纹”(粗体):0 1 -1
1 0 -1
1 1 1
你的角色(=你,但我想区分你的程序在寻找最佳路径时将做什么和你的角色在选择最佳路径时将做什么)将访问每一个这样的条带两次:一次是在从(0,0)到(m-1,n-1)的路上,一次是在返回的路上。这是因为每一个合法的移动从一个带到相邻带在允许的方向。
因此,对于每个条带,从单元素条带开始(0,0),并以单元素条带结束(m=1,n=1),程序将考虑该条中所有可能的元素对-调用它们(I1,J1)和(I2,J2)-并找到可以从(0,0)到(I1)的路径上获得的最大的不同的金币数。j1)加上从(i2,j2)返回到(0,0)的路径对于每个条带,将结果存储在矩阵中,以便它可以用于计算下一条带的结果。(完成一个条带后,可以放弃其上一条带的结果。)
特殊情况:
确保支持两个元素都相同的“退化”对,也就是说,其中i1=i2。对于这样的一对,如果元素包含一枚金币,请确保只计算一次。
一定要区分不可能的部分路径(其中(i1,j1)或(i2,j2)是一个障碍物,或者只能通过障碍物到达)和不包含任何硬币的部分路径。否则,您将错误处理以下情况:
0 0 -1
0 -1 1
0 0 0
其中正确答案是0,因为实际上无法找到唯一的金币。