Chi Phí Leo Thang Tối Thiểu

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
11
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Một cầu thang có $N$ bậc được đánh số từ $0$ đến $N-1$, bậc thứ $i$ có chi phí là $cost[i]$. Sau khi trả chi phí tại bậc $i$, bạn có thể bước lên $1$ hoặc $2$ bậc.

Bạn có thể bắt đầu từ bậc $0$ hoặc bậc $1$ (không mất phí vào bậc xuất phát, chỉ mất phí khi rời khỏi bậc đó). Hãy tìm tổng chi phí nhỏ nhất để lên tới đỉnh cầu thang (vị trí $N$).

Công thức quy hoạch động: $dp[i] = \min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])$.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($2 \le N \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên không âm $cost[0], cost[1], \dots, cost[N-1]$ ($0 \le cost[i] \le 10^4$).
Dữ liệu ra
  • In ra tổng chi phí nhỏ nhất để tới đỉnh $N$.
Ví dụ
Input Output
3\n10 15 20 15
10\n1 100 1 1 1 100 1 1 100 1 6
Giới hạn
  • $2 \le N \le 10^5$
  • $0 \le cost[i] \le 10^4$
Draft saved