LeetCode 63 求教
来源:9-6 0-1背包问题的优化和变种
qq_山上山_0
2020-05-25
啵啵老司,自己感觉没错啊~(c#);
用递归做的;之前类似的62题也是只有递归通过,但是动规的没通过
public class Solution {
int[,] a;
public int UniquePathsWithObstacles(int[][] obstacleGrid)
{
int m = obstacleGrid.Length;
int n = obstacleGrid[0].Length;
a = new int[m, n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (obstacleGrid[i][j] == 1)
a[i, j] = 1;
else
a[i, j] = -1;
}
}
return UniquePath(m - 1, n - 1);
}
public int UniquePath(int m, int n)
{
if(m == 0 && n == 0)
{
if(a[0, 0] == 1)
return 0;
else
return 1;
}
if (m == 0)
{
for (int i = 0; i <= n; i++)
{
if (a[0, i] == 1)
{
return 0;
}
else
a[m, n] = UniquePath(m, Math.Max(n - 1, 0));
}
return 1;
}
if (n == 0)
{
for (int i = 0; i <= m; i++)
{
if (a[i, 0] == 1)
{
return 0;
}
else
{
a[m, n] = UniquePath(Math.Max(m - 1, 0), n);
}
}
return 1;
}
if (a[m, n] == 1)
return 0;
if (a[m, n] == -1)
a[m, n] = UniquePath(Math.Max(m - 1, 0), n) + UniquePath(m, Math.Max(n - 1, 0));
return a[m, n];
}
}
写回答
1回答
-
liuyubobobo
2020-05-26
不能通过的测试用例规模这么小。
自己实际在本地使用这个测试用例跟一下,为什么最后的结果是 0?不是 2?在哪一步计算错了?为什么错了?
进步就在这个过程中哦。
加油!:)
00
相似问题
leetcode 22 号 括号生成问题
回答 2
LeetCode 70 爬楼梯
回答 1