Треугольник

Задача:

Дан триугольник, нужно найти минимальную сумму пути от верхнего елемента до нижнего. Каждый шаг можна осуществлять только на соседние значения, которые лежат в нижнем ряду триугольника.

К примеру, дан следующий триугольник:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

Минимальная сумма пути будет 11( 2 + 3 + 5 + 1 = 11).

Пожелания:

Бунусы тем кто сможет решить задачу с использованием лиш O(n) дополнительной памяти, где n - число рядов триугольника.

Решение:

public int minimumTotal(List<List<Integer>> triangle) {
  if (triangle.size() == 0) {
    return 0;
  }
  int min = 0, prev = 0, cur = 0;
  int[] result = new int[triangle.size()];
  for (int i = 1; i < result.length; i++) {
    result[i] = Integer.MAX_VALUE;
  }
  result[0] = triangle.get(0).get(0);

  List<Integer> list;
  for (int i = 1; i < triangle.size(); i++) {
    list = triangle.get(i);
    prev = result[0];
    result[0] += list.get(0);
    for(int j = 1; j < list.size(); j++) {
      cur = result[j];
      if (cur > prev) {
        result[j] = list.get(j) + prev;
      } else {
        result[j] += list.get(j);
      }
      prev = cur;
    }
  }

  min = result[0];
  for (int i = 1; i < result.length; i++) {
    if (min > result[i]) {
      min = result[i];
    }
  }
  return min;
}

Можно эту задачу решить рекурсивно, но только это будет очень долго, так как рекурсия будет проходить по каждому значению в триугольнике. Но я все равно оставлю этот код на рассмотрение. Если кто-то может что-то поменять, тогода пишите комментарии.

public int minimumTotalRecursivly(List<List<Integer>> triangle) {
	if (triangle.size() == 0) {
		return 0;
	}
	
	int sum = triangle.get(0).get(0);
	sum += FindDepthMin(triangle, 0, 0);
	
	return sum;
}

public int FindDepthMin(List<List<Integer>> list, int depth, int index) {
	if (depth == list.size() - 1) {
		return 0;
	}
	int left = list.get(depth + 1).get(index);
	int right = list.get(depth + 1).get(index+1);
	
	left += FindDepthMin(list, depth + 1, index);
	right += FindDepthMin(list, depth + 1, index + 1);
	

	return left >= right ? right : left;
}
LikeMe: