nikulin_artyom1

dp[1][0] = 1e9; - устанавливаем значение dp[1][0] равным 1e9 (это очень большое число, как миллиард). Это значит, что считаем, что соединить первый гвоздик с другим гвоздиком невозможно (очень дорого).
dp[1][1] = 0; - устанавливаем значение dp[1][1] равным 0. Это значит, что если не соединяем первый гвоздик ни с каким другим, то длина ниточки равна нулю.

for (int i = 2; i <= n; i++) - этот цикл проходит по всем гвоздикам, начиная со второго и до последнего.
dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + (pos[i] - pos[i - 1]); - находим минимальную длину ниточки для текущего гвоздика i, если соединяем его с предыдущим гвоздиком i-1. Берём минимальное значение из dp[i - 1][0] и dp[i - 1][1] (это минимальная длина ниточки для предыдущего гвоздика) и добавляем расстояние между текущим и предыдущим гвоздиком (pos[i] - pos[i - 1]).
dp[i][1] = dp[i - 1][0]; - устанавливаем значение dp[i][1] равным dp[i - 1][0]. Это значит, что если не соединяем текущий гвоздик с предыдущим, то минимальная длина ниточки для текущего гвоздика равна минимальной длине ниточки для предыдущего гвоздика, когда он был соединен.

Добавлено через 3 минуты
Дополнительно:
dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + (pos[i] - pos[i - 1]);:
Смотрим на предыдущий гвоздик i-1.
Берём минимальную длину ниточки из двух вариантов: dp[i - 1][0] и dp[i - 1][1].
Добавляем расстояние между текущим гвоздиком i и предыдущим гвоздиком i-1.
Это даёт нам минимальную длину ниточки, если соединяем текущий гвоздик с предыдущим.

dp[i][1] = dp[i - 1][0];:
Берём значение dp[i - 1][0].
Это минимальная длина ниточки для предыдущего гвоздика, когда он был соединен.
Это значение становится минимальной длиной ниточки для текущего гвоздика, если не соединяем его с предыдущим.

Вернуться к обсуждению:
Найти минимальную длину нитей соединяющих гвоздики C++

0