SS
одна формула - в excel легче чем на с++
Size: a a a
2021 March 22
KS
Sergej Sheryaev
одна формула - в excel легче чем на с++
так это то же дп написал, лол
k
если красный - очень дорогой, зеленый - очень дешевый, а фиолетовый - средне дорогой, то тебе может быть выгодней перейти красный и пойти по зеленому пути, чем весь путь идти по средне дорогому
KS
если красный - очень дорогой, зеленый - очень дешевый, а фиолетовый - средне дорогой, то тебе может быть выгодней перейти красный и пойти по зеленому пути, чем весь путь идти по средне дорогому
извини слишком сложно нарисовано, поверю на слово
k
то что ты написал - это путь по синей стрелке
KS
почему я написал по синей?
KS
я обошел всю матрицу
k
потому что красный преграждает путь твоему алгоритму к зеленому
k
а, стоп
q
ето типичная таска на дп
q
там где король ходит, черепашка ходит
q
кто еще не ходил по этой табличке
KS
там где король ходит, черепашка ходит
рыцарь)
q
лучше загуглить черепашку
q
дп напиши,
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
a[i][j] = min(a[i-1][j],a[i][j-1])
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
a[i][j] = min(a[i-1][j],a[i][j-1])
можно вроде за конст тоже
q
ой, конста по памяти
KS
q
если захерачить переменные под те клетки, откуда он шагает
q
и каждый раз там обновлять
KS
типа сверху и слева? Кажись не выйдет