C# accepted, I am using DP with a map, why is it so slow ?


  • 0
    R

    My accepted C# run at 600ms, the usual accepted C# are around 200ms

    I am using dynamic planning, also a map to store the min path values,

    How can I improve the speed based on current implementation?

    public int MinPathSum(int[,] grid)
    {
        int rowCount = grid.GetLength(0);
        int columnCount = grid.GetLength(1);
        int[,] map = InitMap(rowCount, columnCount);
    
        int i = 0;
        int j = 0;
        int currentSum = 0;
        CalculateMinPath(grid, map, currentSum, i, j, rowCount, columnCount);
    
        return map[rowCount - 1, columnCount - 1];
    }
    
    public int[,] InitMap(int rowCount, int columnCount)
    {
        int[,] map = new int[rowCount, columnCount];
        for (int i = 0; i < rowCount; i++)
        {
            for (int j = 0; j < columnCount; j++)
            {
                map[i, j] = Int32.MaxValue;
            }
        }
        return map;
    }
    
    public void CalculateMinPath(
        int[,] grid, int[,] map, int currentSum, int i, int j, int rowCount, int columnCount)
    {
        int current = currentSum + grid[i, j];
        if (current >= map[i, j])
        {
            // give up this path, since the sum is already bigger than the current min
            return;
        }
    
        // keep current min
        map[i, j] = current;
    
        // if can go right
        if (j + 1 < columnCount)
        {
            CalculateMinPath(grid, map, current, i, j + 1, rowCount, columnCount);
        }
    
        // if can go down
        if (i + 1 < rowCount)
        {
            CalculateMinPath(grid, map, current, i + 1, j, rowCount, columnCount);
        }
    }

  • 0
    L
    This post is deleted!

Log in to reply
 

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