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

不能通过的测试用例规模这么小。

//img.mukewang.com/szimg/5ecc1c1f09fd5b4005210225.jpg


自己实际在本地使用这个测试用例跟一下,为什么最后的结果是 0?不是 2?在哪一步计算错了?为什么错了?


进步就在这个过程中哦。


加油!:)

0
0

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程