Сложность: easy
Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа.
Пример:
Input: cost = [10,15,20]
Output: 15
👨💻 Алгоритм:
1⃣Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки.
2⃣Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек.
3⃣Вернуть минимальную стоимость достижения вершины.
😎 Решение:
def minCostClimbingStairs(cost):
n = len(cost)
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
return min(dp[-1], dp[-2])
Ставь 👍 и забирай 📚 Базу знаний