[leetcode]120. 三角形最小路径和

1.题目:
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

2.代码:

int *minSum;
int minimumTotal(int** triangle, int triangleRowSize, int *triangleColSizes) {
    minSum=triangle[triangleRowSize-1];
    for(int i=triangleRowSize-2;i>=0;i--){
        for(int j=0;j<=i;j++){
            int x=triangle[i][j]+minSum[j];
            int y=triangle[i][j]+minSum[j+1];
            minSum[j]=x<y?x:y;
        }
    }
    return minSum[0];
}

3.知识点:

动态规划

上一篇:配置AIX系统互信关系


下一篇:120. 三角形最小路径和