746. Min cost climb stairs

746_solution1_memo.c

#include <stdlib.h>

static int min(int a, int b) { return a < b ? a : b; }

static int costs(int i, int *cost, int *memo) {
  if (i <= 1)
    return 0; // start on step 0 or 1 for free
  if (memo[i] != -1)
    return memo[i];
  return memo[i] = min(costs(i - 1, cost, memo) + cost[i - 1],
                       costs(i - 2, cost, memo) + cost[i - 2]);
}

int minCostClimbingStairs(int *cost, int costSize) {
  int *memo = malloc((costSize + 1) * sizeof(int));
  for (int i = 0; i <= costSize; i++)
    memo[i] = -1;
  int res = costs(costSize, cost, memo);
  free(memo);
  return res;
}

746_solution2_tab.c

#include <stdlib.h>

static int min(int a, int b) { return a < b ? a : b; }

int minCostClimbingStairs(int *cost, int costSize) {
  int n = costSize;
  int *dp = malloc((n + 1) * sizeof(int));
  dp[0] = 0; // start on step 0 for free
  dp[1] = 0; // start on step 1 for free

  for (int i = 2; i <= n; i++) {
    dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
  }
  int res = dp[n]; // n = the top, one past the last step
  free(dp);
  return res;
}

746_solution1_memo.cpp

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
  vector<int> memo;

  int costs(int i, vector<int> &cost) {
    if (i <= 1)
      return 0; // start on step 0 or 1 for free
    if (memo[i] != -1)
      return memo[i];
    return memo[i] = min(costs(i - 1, cost) + cost[i - 1],
                         costs(i - 2, cost) + cost[i - 2]);
  }

public:
  int minCostClimbingStairs(vector<int> &cost) {
    memo.assign(cost.size() + 1, -1);
    return costs(cost.size(), cost);
  }
};

746_solution2_tab.cpp

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  int minCostClimbingStairs(vector<int> &cost) {
    int n = cost.size();
    vector<int> dp(n + 1);
    dp[0] = 0; // start on step 0 for free
    dp[1] = 0; // start on step 1 for free

    for (int i = 2; i <= n; i++) {
      dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[n]; // n = the top, one past the last step
  }
};

746_solution1_memo.go

package dp

func minCostClimbingStairs(cost []int) int {
    memo := make([]int, len(cost)+1)
    for i := range memo {
        memo[i] = -1
    }

    var costs func(i int) int
    costs = func(i int) int {
        if i <= 1 {
            return 0 // start on step 0 or 1 for free
        }
        if memo[i] != -1 {
            return memo[i]
        }
        memo[i] = min(costs(i-1)+cost[i-1], costs(i-2)+cost[i-2])
        return memo[i]
    }

    return costs(len(cost))
}

746_solution2_tab.go

package dp

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int, n+1) // dp[0] = dp[1] = 0: start on step 0 or 1 for free

    for i := 2; i <= n; i++ {
        dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
    }
    return dp[n] // n = the top, one past the last step
}

746_solution1_memo.java

import java.util.Arrays;

class Solution {
    private int[] memo;

    private int costs(int i, int[] cost) {
        if (i <= 1)
            return 0; // start on step 0 or 1 for free
        if (memo[i] != -1)
            return memo[i];
        return memo[i] = Math.min(costs(i - 1, cost) + cost[i - 1],
                costs(i - 2, cost) + cost[i - 2]);
    }

    public int minCostClimbingStairs(int[] cost) {
        memo = new int[cost.length + 1];
        Arrays.fill(memo, -1);
        return costs(cost.length, cost);
    }
}

746_solution2_tab.java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = 0; // start on step 0 for free
        dp[1] = 0; // start on step 1 for free

        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n]; // n = the top, one past the last step
    }
}

746_solution1_memo.js

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
  const memo = new Array(cost.length + 1).fill(-1);

  const costs = (i) => {
    if (i <= 1) return 0; // start on step 0 or 1 for free
    if (memo[i] !== -1) return memo[i];
    return (memo[i] = Math.min(
      costs(i - 1) + cost[i - 1],
      costs(i - 2) + cost[i - 2],
    ));
  };

  return costs(cost.length);
};

746_solution2_tab.js

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
  const n = cost.length;
  const dp = new Array(n + 1).fill(0); // dp[0] = dp[1] = 0: start on step 0 or 1 for free

  for (let i = 2; i <= n; i++) {
    dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
  }
  return dp[n]; // n = the top, one past the last step
};

746_solution1_memo.py

from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        memo = [-1] * (len(cost) + 1)

        def costs(i: int) -> int:
            if i <= 1:
                return 0  # start on step 0 or 1 for free
            if memo[i] != -1:
                return memo[i]
            memo[i] = min(costs(i - 1) + cost[i - 1], costs(i - 2) + cost[i - 2])
            return memo[i]

        return costs(len(cost))

746_solution2_tab.py

from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 1)  # dp[0] = dp[1] = 0: start on step 0 or 1 for free

        for i in range(2, n + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        return dp[n]  # n = the top, one past the last step

746_solution1_memo.rs

impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let mut memo = vec![-1; cost.len() + 1];
        Self::costs(cost.len(), &cost, &mut memo)
    }

    fn costs(i: usize, cost: &[i32], memo: &mut Vec<i32>) -> i32 {
        if i <= 1 {
            return 0; // start on step 0 or 1 for free
        }
        if memo[i] != -1 {
            return memo[i];
        }
        memo[i] = (Self::costs(i - 1, cost, memo) + cost[i - 1])
            .min(Self::costs(i - 2, cost, memo) + cost[i - 2]);
        memo[i]
    }
}

746_solution2_tab.rs

impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let n = cost.len();
        let mut dp = vec![0; n + 1]; // dp[0] = dp[1] = 0: start on step 0 or 1 for free

        for i in 2..=n {
            dp[i] = (dp[i - 1] + cost[i - 1]).min(dp[i - 2] + cost[i - 2]);
        }
        dp[n] // n = the top, one past the last step
    }
}