C# accepted, 56ms, using Dynamic Planning (DP)


  • 0
    R
    public int UniquePaths(int m, int n)
    {
        int i = 0;
        int j = 0;
        int[,] map = new int[m, n];
    
        return CalculateUniquePaths(i, j, m, n, map);
    }
    
    public int CalculateUniquePaths(int i, int j, int rowCount, int columnCount, int[,] map)
    {
        if (i >= rowCount || j >= columnCount)
        {
            return 0;
        }
    
        if (i == rowCount - 1 && j == columnCount - 1)
        {
            map[i, j] = 1;
        }
        else
        {
            int right = 0;
            if (j + 1 < columnCount)
            {
                right = map[i, j + 1] == 0 ?
                        CalculateUniquePaths(i, j + 1, rowCount, columnCount, map)
                        : map[i, j + 1];
                map[i, j + 1] = right;
            }
    
            int down = 0;
            if (i + 1 < rowCount)
            {
                down = map[i + 1, j] == 0 ?
                       CalculateUniquePaths(i + 1, j, rowCount, columnCount, map)
                       : map[i + 1, j];
                map[i + 1, j] = down;
            }
    
            map[i, j] = right + down;
        }
    
        return map[i, j];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.