746. Min Cost Climbing Stairs

leetcode easy

#array#csharp#dynamic-programming#easy#leetcode#math

Task

Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа.

Пример:

Input: cost = [10,15,20]

Output: 15

C# solution

matched/original

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + Math.Min(dp[i - 1], dp[i - 2]);
        }
        return Math.Min(dp[n - 1], dp[n - 2]);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int>& dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
        }
        return min(dp[n - 1], dp[n - 2]);
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
        }
        return Math.min(dp[n - 1], dp[n - 2]);
    }
}

JavaScript solution

matched/original

var minCostClimbingStairs = function(cost) {
    let dp = cost.slice();
    for (let i = 2; i < cost.length; i++) {
        dp[i] += Math.min(dp[i - 1], dp[i - 2]);
    }
    return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
};

Python solution

matched/original

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])

Go solution

matched/original

package main

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int, n)
    copy(dp, cost)
    for i := 2; i < n; i++ {
        dp[i] += min(dp[i-1], dp[i-2])
    }
    return min(dp[n-1], dp[n-2])
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Explanation

Algorithm

Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки.

Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек.

Вернуть минимальную стоимость достижения вершины.

😎