三角形最小路径和

int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) {
    int dp[201][200];
    dp[0][0]=triangle[0][0];
    for (int i=1; i<triangleRowLen; i++) {
           dp[i][0]=dp[i-1][0]+triangle[i][0];
    }
    for (int i=1; i<triangleRowLen; i++) {
        for (int j=1; j<triangleColLen[i]; j++) {
             if (j==triangleColLen[i]-1) {
                 dp[i][j]=dp[i-1][j-1]+triangle[i][j];
             }
             else {
                 dp[i][j]=(dp[i-1][j-1]<dp[i-1][j]?dp[i-1][j-1]:dp[i-1][j])+triangle[i][j];
             }
        }
    }
    int min=dp[triangleRowLen-1][0];
    for (int i=0; i<triangleColLen[triangleRowLen-1]; i++) {
         if(dp[triangleRowLen-1][i]<min){
            min=dp[triangleRowLen-1][i];
         }
    }
    return min;
    
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param triangle int整型二维数组 
 * @param triangleRowLen int triangle数组行数
 * @param triangleColLen int* triangle数组列数
 * @return int整型
 */
int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) {
    int dp[201][200] = {0};
    int min=0;
    dp[0][0] = triangle[0][0];
    //先记录整个第一列的dp值
    for(int i=1; i<triangleRowLen; i++)
        dp[i][0] = dp[i-1][0] + triangle[i][0];
    //然后每一个数都是起点到该店的最小路径，为上一个或前一个的最小路径加上自己
    for(int i=1; i<triangleRowLen; i++)
    {
        for(int j=1; j<(triangleColLen[triangleRowLen-1]); j++)
        {
            if(j == triangleColLen[i]-1)
            {
                dp[i][j] = dp[i-1][j-1]+triangle[i][j];
                continue;
            }
            min = dp[i-1][j]<dp[i-1][j-1]?dp[i-1][j]:dp[i-1][j-1];
            dp[i][j] = min+triangle[i][j];
        }
    }
    min = dp[triangleRowLen-1][0];
    for(int j=0; j<(triangleColLen[triangleRowLen-1]); j++)
    {
        if(dp[triangleRowLen-1][j]<min)
        min = dp[triangleRowLen-1][j];
    }
    return min;
    // write code here
}