Đường đi nhỏ nhất trong tam giác số
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một tam giác số gồm $N$ hàng, hàng thứ $i$ ($1 \le i \le N$) có $i$ số nguyên. Bắt đầu từ đỉnh tam giác (hàng $1$, cột $1$), ở mỗi bước từ vị trí $(i, j)$ bạn có thể đi xuống vị trí $(i+1, j)$ hoặc $(i+1, j+1)$.
Hãy tìm đường đi từ đỉnh xuống hàng cuối cùng (hàng $N$) sao cho tổng các số trên đường đi là nhỏ nhất.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 500$).
- $N$ dòng tiếp theo, dòng thứ $i$ chứa $i$ số nguyên có giá trị tuyệt đối không quá $10^6$.
Dữ liệu ra
Một số nguyên duy nhất là tổng đường đi nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
4<br>2<br>3 4<br>6 5 7<br>4 1 8 3 |
11 |
Giới hạn
- $1 \le N \le 500$
Community Discussion