C solution using DP that works for any size grid (not just <=100) - ~0ms


  • 0
    A
    int uniquePaths(int m, int n) {
        int **grid;
        int i, j, leftIdx, topIdx, result;
        
        grid = (int **)malloc(m * sizeof(int *));
        
        for (i = 0; i < m; i++) {
            grid[i] = (int *)calloc(n, sizeof(int));
        }
        
        grid[0][0] = 1;
        for (i = 0; i < m; i ++) {
            for (j = 0; j < n; j++) {
                // check left
                leftIdx = i - 1;
                if (leftIdx >= 0) {
                    grid[i][j] += grid[leftIdx][j];
                }
                
                // check top
                topIdx = j - 1;
                if (topIdx >= 0) {
                    grid[i][j] += grid[i][topIdx];
                }
            }
        }
        
        result = grid[m-1][n-1];
        
        for (i = 0; i < m; i++) {
            free(grid[i]);
            grid[i] = NULL;
        }
        
        free(grid);
        grid = NULL;
        
        return result;
    }
    

Log in to reply
 

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