Устранение неполадок динамического программирования

Question

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

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

Это пример динамического программирования. Но очень сложная или запутанная концепция для меня, когда я приступаю к упражнению. Я смотрел видео и читал учебники в Интернете, и сначала это кажется довольно простым, но когда я подхожу к проблеме, я полностью теряюсь. Так я нашел решение в оперативном режиме и использует нижний подход:

public init minmumTotal(ArrayList<ArrayList<Integer>> triangle) { 
     if (triangle.size() == 0 || triangle == null) 
        return 0; 
    int[] dp = new int[triangle.size()+1]; // store each index’s total 
     for (int i = triangle.size()-1; i >=0; i--) { 
      for (int j = 0; j < triangle.get(i).size(); j++) { 
       // first round: dp[j], dp[j+1] are both 0 
       dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j); 
      } 
     } 
      return dp[0]; 
     } 

кажется легким после прохождения через раствор. Но можно ли это сделать, используя подход сверху вниз? И может ли кто-нибудь объяснить, почему нижний подход лучше, чем подход сверху вниз? Также когда целесообразно использовать сверху вниз или снизу вверх? А также, поскольку вопрос упоминается, что каждый "Each step you may move to adjacent numbers on the row below." Означает ли это, что для каждой строки повторяется весь столбец, прежде чем я перехожу в следующую строку?

Answer 1

Я не уверен, что это решение считается динамическим программированием, но я думаю, что он очень эффективен.

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

Начало:

2 
    3 4 
6 5 7 
4 1 8 3 

Шаг 1:

2 
    3 4 
7 6 10 

Шаг 2:

2 
    9 10 

Шаг 3:

11 

Answer 2

Немного не по теме, но первая инструкция if в этом решении должна быть обернута, если вы действительно хотите правильно обрабатывать NullPointerExceptions.

Итак, я попробовал себя под верхним подходом, и есть пара проблем.

Во-первых, как уже сказал marstran, у вас больше номеров в конце и нужно выполнить минимальный поиск.

Во-вторых, подход «снизу вверх» использовал дополнительное поле массива, чтобы убедиться, что он не будет работать с исключениями IndexOutOfBound. Я действительно не нашел хороший способ сделать это сверху вниз (подход на нижнем уровне имеет то преимущество, что вы всегда знаете, что у вас есть два числа, на которые нужно смотреть (левый ребенок и правый ребенок), при этом сверху вниз подходит множество узлов не имеют правого или левого родителя). Итак, есть пара дополнительных if-утверждений.

public static int minimumTotal(ArrayList<ArrayList<Integer>> triangle) { 
    if (triangle == null || triangle.isEmpty()) return 0; 

    int[] results = new int[triangle.size()]; 

    for (int i = 0; i < triangle.size(); i++) { 
     ArrayList<Integer> line = triangle.get(i); 

     for (int j = line.size() - 1; j >= 0; j--) { 
      if (j == 0) results[j] = line.get(j) + results[j]; 
      else if (j >= i) results[j] = line.get(j) + results[j - 1]; 
      else results[j] = line.get(j) + Math.min(results[j], results[j - 1]); 
     } 
    } 

    int minimum = results[0]; 
    for (int i = 1; i < results.length; i++) { 
     if (results[i] < minimum) { 
      minimum = results[i]; 
     } 
    } 

    return minimum; 
} 

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

Имейте в виду, что никто не заставляет вас использовать только 1d-массив для ваших результатов. Если эта концепция слишком сложна, вы можете просто использовать массив 2d. Это увеличит количество кода, который вам нужно написать, но, может быть, немного легче придумать.