İçeriğe geç

Grid boyunca en ucuz yol

Kolay#grid-dp#2d-dp~20 dk

Görev tanımı

Problem

Bir grid'in her hücresinde negatif olmayan bir maliyet var. Sol üst hücreden başlıyorsun ve yalnız sağa ya da aşağı giderek sağ alt hücreye ulaşmalısın. İlk ve son hücreler dahil, içinden geçtiğin hücrelerin maliyetlerinin mümkün olan en küçük toplamını döndür.

Örnekler

Input:  grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Neden: sağ, sağ, aşağı, aşağı 1, 3, 1, 1, 1'i ziyaret eder ve ortadaki 5'ten kaçınır
Input:  grid = [[2, 1, 4], [3, 1, 1]]
Output: 5
Neden: sağ, aşağı, sağ 2, 1, 1, 1'i ziyaret eder
Input:  grid = [[7]]
Output: 7
Neden: edge case: başlangıç aynı zamanda bitiş

İpuçları

0 / 3

Hedef zaman
O(rows · cols)
Hedef alan
O(rows · cols)

Kısıtlar

  • every cell cost is non-negative

Kodda değil de fikirde mi takıldın? Grid'lerde DP bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case