Using only one single array to achieve DP accepted best in C


  • 1
    int minPathSum(int** grid, int rSize, int cSize)
    {
        int *sums, pre;
        sums = (int*)malloc(sizeof(int)*cSize);
        sums[0] = grid[0][0];
        for(int i = 1; i < cSize; i++)
            sums[i] = sums[i-1] + grid[0][i];
        for(int r=1; r<rSize; r++)
        {
            for(int c=0; c<cSize; c++)
            {
                int min = sums[c];
                if(c && min > pre)
                    min = pre;
                sums[c] = min+grid[r][c];
                pre = sums[c];
            }
        }
        return sums[cSize-1];
    }

  • 0
    S

    @LHearen gorgeous solution only O(n) space cost.


  • 1
    S

    @LHearen Inspired by yours, I have the following solution in C++.

    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            if(grid.empty()) return 0;
            int rowSize = grid.size(), colSize = grid[0].size();
            int *sums = new int[colSize]();
            partial_sum(grid[0].begin(), grid[0].end(), sums);
            for(int r = 1; r < rowSize; ++r){
                sums[0] += grid[r][0];
                for(int c = 1; c < colSize; ++c)
                    sums[c] = min(sums[c], sums[c-1])+grid[r][c];
            }
            return sums[colSize-1];
        }
    };
    

Log in to reply
 

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