Каково максимальное количество золота, которое мудрец собрал, проходя по комнате размером n×m клеток и забирая золото

Для решения данной задачи нам необходимо пройти по каждой клетке комнаты и собрать максимально возможное количество золота. Мы можем использовать динамическое программирование для нахождения оптимального решения.

Предлагаю следующий алгоритм:

1. Создаем двумерный массив dp размером n×m, где каждый элемент dp[i][j] будет содержать максимальное количество золота, которое можно собрать, находясь в клетке с координатами (i, j).
2. Инициализируем первую строку и первый столбец массива dp.
a. dp[0][j] = план[0][j], где план[0][j] представляет количество золота в клетке (0, j).
b. dp[i][0] = план[i][0], где план[i][0] представляет количество золота в клетке (i, 0).
3. Для каждой клетки с координатами (i, j), начиная с i=1 и j=1, находим максимальное количество золота, которое можно собрать:
a. dp[i][j] = план[i][j] + max(dp[i-1][j], dp[i][j-1]), где max(a, b) возвращает большее значение из a и b.
4. В конечном итоге, значение dp[n-1][m-1] будет содержать максимальное количество золота, которое мудрец сможет собрать.

Вот пошаговое решение задачи:

1. Инициализируем массивы план и dp:
\[
\begin{align*}
\text{план} &= \left[\begin{array}{ccc}
1 & 3 & 1 \\
2 & 2 & 2 \\
3 & 0 & 0 \\
\end{array}\right] \\
\text{dp} &= \left[\begin{array}{ccc}
0 & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & 0 \\
\end{array}\right]
\end{align*}
\]

2. Инициализируем первую строку массива dp:
\[
\begin{align*}
\text{dp} &= \left[\begin{array}{ccc}
1 & 4 & 5 \\
0 & 0 & 0 \\
0 & 0 & 0 \\
\end{array}\right]
\end{align*}
\]

3. Инициализируем первый столбец массива dp:
\[
\begin{align*}
\text{dp} &= \left[\begin{array}{ccc}
1 & 4 & 5 \\
3 & 0 & 0 \\
6 & 0 & 0 \\
\end{array}\right]
\end{align*}
\]

4. Вычисляем значения массива dp для каждой клетки, начиная со второй строки и второго столбца:
\[
\begin{align*}
\text{dp} &= \left[\begin{array}{ccc}
1 & 4 & 5 \\
3 & 6 & 7 \\
6 & 0 & 0 \\
\end{array}\right]
\end{align*}
\]

5. Окончательный результат: максимальное количество золота, которое мудрец сможет собрать, равно 7.

Таким образом, ответ на задачу - 7.