题解 | #三角形最小路径和#

/**
动态规划思想，求每个位置上最小的路径，如果是经过triangle[n][0]上面的，那么到他只能从triangle[n-1][0]下来，
经过triangle[n][1~i],只能从它头上两个顶点来，那么找到最小值就行了，
从而得到最后一row，取其中最小值即可。
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param triangle int整型二维数组
 * @param triangleRowLen int triangle数组行数
 * @param triangleColLen int* triangle数组列数
 * @return int整型
 */
#include <stdio.h>
int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) {
    if (!triangle[0][0]) {
        return 0;
    }
    // write code here
    for (int i = 1; i < triangleRowLen; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                triangle[i][j] += triangle[i - 1][j];
            }
            if (j == i) {
                triangle[i][j] += triangle[i - 1][j - 1];
            }
            if (j > 0 && j < i) {
                triangle[i][j] = triangle[i - 1][j - 1] < triangle[i - 1][j] ? triangle[i - 1][j
                                 - 1] + triangle[i][j] : triangle[i - 1][j] + triangle[i][j];
            }
        }
    }

    int min = triangle[triangleRowLen - 1][0];
    for (int i = 0; i < triangleRowLen; i++) {
        min = min < triangle[triangleRowLen - 1][i] ? min : triangle[triangleRowLen -
                1][i];
    }
    return min;
}