Динамическое программирование - максимальный бриллиант

Question

Я пытался решить одну проблему интервью:

Дана матрица из n*n. Каждая ячейка содержит 0, 1, -1. 0 означает, что алмаза нет, но путь есть. 1 означает, что в этом месте находится ромб, а путь -1 означает, что путь заблокирован. Теперь вы начинаете с 0,0 и достигаете последней ячейки, а затем возвращаетесь к 0,0, собирая максимальное количество алмазов. Идя к последней клетке, вы можете двигаться только вправо и вниз. Возвращаясь назад, вы можете двигаться только влево и вверх.

Я решил проблему, но я не уверен, что это оптимальное решение. Что я делаю, так это

• Это вместо того, чтобы вернуться от последней ячейки к первой ячейке, я разрешаю 2 итерации от начальной ячейки до последней ячейки.
• Когда я сделаю первую итерацию, я попытаюсь получить максимальное количество алмазов с помощью динамического программирования, и после этого я удалю те алмазы, которые собраны на первой итерации, из матрицы, то есть: установите значение матрицы 0 из 1.
• Во второй итерации я буду вызывать тот же метод, что и в первой итерации, но с измененной матрицей.
• И вернуть сумму обоих звонков.

Любые предложения о правильности? Я написал код, если это необходимо, я поделюсь.

Answer 1

Ваш алгоритм не верен. Вот контрпример:

<table border="1">
  <tr>
    <td>1</td>
    <td>1</td>
    <td>1</td>
  </tr>
  <tr>
    <td>1</td>
    <td>1</td>
    <td>1</td>
  </tr>
   <tr>
    <td>0</td>
    <td>1</td>
    <td>1</td>
  </tr>
</table>

Максимальный путь сверху вниз соберет 5 алмазов и может быть таким:

<table border="1">
  <tr>
    <td>*</td>
    <td>*</td>
    <td>_</td>
  </tr>
  <tr>
    <td>_</td>
    <td>*</td>
    <td>*</td>
  </tr>
   <tr>
    <td>_</td>
    <td>_</td>
    <td>*</td>
  </tr>
</table>

Но тогда ваша вторая итерация может собрать только еще 2.

Таким образом, ваш алгоритм вернет максимальное значение 7.

Но есть решение, с помощью которого вы можете собрать 8.

Например, если путь вниз выглядит так:

<table border="1">
  <tr>
    <td>*</td>
    <td>_</td>
    <td>_</td>
  </tr>
  <tr>
    <td>*</td>
    <td>*</td>
    <td>_</td>
  </tr>
   <tr>
    <td>_</td>
    <td>*</td>
    <td>*</td>
  </tr>
</table>

Answer 2

Вы можете использовать динамическое программирование. Вам нужно заполнить матрицу размерами [2*n-1,n,n], где DP[A,B,C] соответствует наилучшему результату для диагонали (или общей длины пути) A и первого пути в положение B, а второго в положение C,

Вы начинаете с DP [0,0,0] и заканчиваете DP[2*n-1,0,0]. Ответ будет DP[2*n-1,0,0].

DP[l,i,j] = MAX(DP[l-1,i,j], DP[l-1,i-1,j], DP[l-1,i,j-1], DP[l-1,i-1,j-1]) + Diamond[i, li] + Diamond[j, lj] и уменьшение на Diamond [j, lj], если i равно j.

И пропустить все места, где путь невозможен.

Общая сложность будет O(N^3)

Answer 3

"Вы начинаете с 0,0 и достигаете последней ячейки, а затем возвращаетесь к 0,0"

== "У вас есть начало от 0,0 до последней ячейки дважды"

а также

d: общее расстояние

х1: х позиция для первого

х2: х позиция для второго

y1: d - x1 // можно опустить

y2: d - x2 // можно опустить

dp[d][x1][x2]: максимальное количество полученных алмазов из ячейки (0, 0) до ячейки (x1, y1) и от ячейки (0, 0) до ячейки (x2, y2)