Min Cost Climbing Stairs

Medium Dynamic Programming

Each stair has a cost. You can start at step 0 or 1 and climb 1 or 2 steps at a time. Find the minimum cost to reach the top.

Sample input

[10, 15, 20]

Sample output

Solution

def min_cost(cost):
    n = len(cost)
    a, b = 0, 0
    for i in range(2, n + 1):
        cur = min(b + cost[i - 1], a + cost[i - 2])
        a, b = b, cur
    return b

print(min_cost([10, 15, 20]))

function minCost(cost) {
  const n = cost.length;
  let a = 0, b = 0;
  for (let i = 2; i <= n; i++) {
    const cur = Math.min(b + cost[i - 1], a + cost[i - 2]);
    a = b;
    b = cur;
  }
  return b;
}

console.log(minCost([10, 15, 20]));

public class Main {
    static int minCost(int[] cost) {
        int n = cost.length;
        int a = 0, b = 0;
        for (int i = 2; i <= n; i++) {
            int cur = Math.min(b + cost[i - 1], a + cost[i - 2]);
            a = b;
            b = cur;
        }
        return b;
    }

    public static void main(String[] args) {
        System.out.println(minCost(new int[]{10, 15, 20}));
    }
}

fun minCost(cost: IntArray): Int {
    val n = cost.size
    var a = 0
    var b = 0
    for (i in 2..n) {
        val cur = minOf(b + cost[i - 1], a + cost[i - 2])
        a = b
        b = cur
    }
    return b
}

fun main() {
    println(minCost(intArrayOf(10, 15, 20)))
}

func minCost(_ cost: [Int]) -> Int {
    let n = cost.count
    var a = 0, b = 0
    if n >= 2 {
        for i in 2...n {
            let cur = min(b + cost[i - 1], a + cost[i - 2])
            a = b
            b = cur
        }
    }
    return b
}

print(minCost([10, 15, 20]))

int minCost(List<int> cost) {
  final n = cost.length;
  int a = 0, b = 0;
  for (var i = 2; i <= n; i++) {
    final x = b + cost[i - 1];
    final y = a + cost[i - 2];
    final cur = x < y ? x : y;
    a = b;
    b = cur;
  }
  return b;
}

void main() {
  print(minCost([10, 15, 20]));
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minCost(const vector<int>& cost) {
    int n = cost.size();
    int a = 0, b = 0;
    for (int i = 2; i <= n; i++) {
        int cur = min(b + cost[i - 1], a + cost[i - 2]);
        a = b;
        b = cur;
    }
    return b;
}

int main() {
    cout << minCost({10, 15, 20}) << endl;
    return 0;
}

#include <stdio.h>

int minCost(int *cost, int n) {
    int a = 0, b = 0;
    for (int i = 2; i <= n; i++) {
        int x = b + cost[i - 1];
        int y = a + cost[i - 2];
        int cur = x < y ? x : y;
        a = b;
        b = cur;
    }
    return b;
}

int main() {
    int cost[] = {10, 15, 20};
    printf("%d\n", minCost(cost, 3));
    return 0;
}