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

• 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];
}
``````

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