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

首先，我一看，这个题目简单，怎么是中等难度呢？

马上奋笔疾书

思路就是从上到下，能选最小就选最小，只走一次。

int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) {

// write code here

int j = 0;

int sum = triangle[0][0];

for (int i = 1; i < triangleRowLen; i++) {

if (triangle[i][j] < triangle[i][j + 1]) {

sum = sum + triangle[i][j];

}else {

sum = sum + triangle[i][j+1];

j = j+1;

}

}

return sum;

}

一提交不对劲呀，还有两个例子没有通过。

仔细想想应该是：

[[1],[1000,0],[-10000,0,1]],这种情况。

走一次不行，那就全试一遍吧。

#include <stdio.h>

#include<malloc.h>

int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) {

printf("%d",triangleRowLen);

// write code here

int** arr2 = (int**)malloc(triangleRowLen * sizeof(int**));

int i, j;

for (i = 0; i < triangleRowLen; i++) {

// 得到行首指针，注意相邻行的内存空间不一定连续

// 但同一行内部元素的内存空间是连续的

arr2[i] = (int*)malloc((i+1) * sizeof(int));

}

// 录入数据

for (i = 0; i < triangleRowLen; i++) {

for (j = 0; j <=i; j++) {

arr2[i][j] = 0; // 快速录入预设数据

}

}

arr2[0][0] = triangle[0][0];

if(triangleRowLen>1){

for ( i = 1; i < triangleRowLen; i++) {

for ( j = 0; j <= i; j++) {

if (j == 0) {

arr2[i][j] = arr2[i - 1][j] + triangle[i][j];

}

if (j > 0 && j < i) {

arr2[i][j] = arr2[i - 1][j - 1] < arr2[i - 1][j] ? arr2[i - 1][j - 1] : arr2[i -

1][j];

arr2[i][j] = arr2[i][j] + triangle[i][j];

}

if (j == i) {

arr2[i][j] = arr2[i - 1][j - 1] + triangle[i][j];

}

}

}

}

int min = arr2[triangleRowLen-1][triangleRowLen-1];

for ( i = 0; i < triangleRowLen; i++) {

if (min > arr2[triangleRowLen-1][i]) {

min = arr2[triangleRowLen-1][i];

}

}

return min;

}