Short DP code in C, with O(n) and O(1) space two solutions


  • 0
    D

    Same idea as this. But can achieve O(1).

    int minimumTotal(int** triangle, int triangleRowSize, int * triangleColSizes) {
        // time: O(m), m is the number of elements in the triangle
        // space: O(1) if store min sums for each element in-place in original array triangle
        //        O(n) if store min sums for each element in a n-long array
        #define MIN(a, b) ((a) < (b) ? (a) : (b))
        int * min_sums = malloc(sizeof(int) * triangleColSizes[triangleRowSize-1]);
        memcpy((char*) min_sums, (char*) triangle[triangleRowSize - 1], sizeof(triangle[0][0]) * triangleColSizes[triangleRowSize - 1]);
        for(int i = triangleRowSize - 2; i >= 0; i--){ // loop from bottom to top
            for(int j = 0; j < triangleColSizes[i]; j++){ // for each element in the row, get min path starting from it to the bottom
                //triangle[i][j] = triangle[i][j] + MIN(triangle[i+1][j], triangle[i+1][j+1]); // in-place store
                min_sums[j] = triangle[i][j] + MIN(min_sums[j], min_sums[j+1]);  // extra space to store
            }
        }
        return min_sums[0];
    }
    

Log in to reply
 

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