120 triange

/*

区别于自顶向下，另一种更简单的做法就是自底向上了。dp方程为
dp[m][n] = min(dp[m + 1][n], dp[m + 1][n + 1]) + triangle[m][n]
我们仍然可以使用一位数组滚动计算。
*/
#define min(a,b) (a<b?a:b)
int minimumTotal(int** triangle, int triangleRowSize, int *triangleColSizes) {

    int *dp = calloc(triangleColSizes[triangleRowSize-1],sizeof(int));
    
    int mintotal ;
    //dp[0] = triangle[0][0];
    for(int i = 0;  i <triangleColSizes[triangleRowSize-1]; i++)
        dp[i] = triangle[triangleRowSize-1][i];

    for(int i = triangleRowSize-2; i >=0; i--)
        for(int j = 0; j < triangleColSizes[i]; j++)
            dp[j] = min(dp[j],dp[j+1])+triangle[i][j];


    return dp[0];       
        
}