题解 | 三角形最小路径和

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param triangle int整型二维数组
 * @param triangleRowLen int triangle数组行数
 * @param triangleColLen int* triangle数组列数
 * @return int整型
 */
int min(int a, int b) {
    if (a < b) {
        return a;
    } else {
        return b;
    }
}
int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) {
    // write code here
    if (triangleRowLen == 1) {
        return triangle[0][0];
    }
    int dp[triangleRowLen][triangleColLen[triangleRowLen-1]];
    for(int i=0;i<triangleRowLen;i++){
        for(int j=0;j<triangleColLen[i];j++){
            dp[i][j]=0;
        }
    }
    for (int i =0;i< triangleRowLen; i++) {
        for (int j = 0; j < triangleColLen[i]; j++) {
            if (i >= j) {
                if (j == 0) {
                    if(i==0){
                        dp[i][j]=triangle[i][j];
                    }else{
                        dp[i][j] = triangle[i][j] + dp[i - 1][j];
                    }
                    
                }
                else if (i == j) {
                    dp[i][j] = triangle[i][j] + dp[i - 1][j - 1];
                }else{
                    dp[i][j] = triangle[i][j]+min(dp[i - 1][j], dp[i - 1][j - 1]);
                }
                
            }
        }
    }
    int min=dp[triangleRowLen-1][0];
    for(int i=0;i<triangleColLen[triangleRowLen-1];i++){
        if(min<dp[triangleRowLen-1][i]){
            min=min;
        }else{
            min=dp[triangleRowLen-1][i];
        }
    }
    return min;
}