Đường đi nhỏ nhất trong tam giác số

General
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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$
Draft saved