746.min-cost-climbing-stairs.md

746. Min Cost Climbing Stairs

Key Insights

We start either from index 0 or 1, and find the min cost when reaching n-th step. There are two way to represent the states:

• to(i) represents the cost to i-th step, then we calculate to(n).
• from(i) represents the cost from i-th step, then we calculate min(from(n - 1), from(n - 2)).

to(i) = min(to(i - 1) + cost[i - 1], to(i - 2) + cost[i - 2])
from(i) = cost[i] + min(from(i - 1), from(i - 2))

To State

The to(i) / dp[i] represents the cost to i-th step:

• To 0 or 1 step cost 0, we don't have to zero cost to 0 or 1.
• The cost to i-th step will be the minimum of to(i - 1) + cost[i - 1] and to(i - 2) + cost[i - 2].
• We calculate to(n) for the result.

// Recursive with memoization
private val memo = hashMapOf<Int, Int>()

fun minCostClimbingStairs(cost: IntArray): Int {
    return to(cost, cost.size)
}

// Top-Down DP
private fun to(cost: IntArray, i: Int): Int {
    if (i == 0 || i == 1) return 0
    if (memo.containsKey(i)) return memo[i]!!
    memo[i] = min(to(cost, i - 1) + cost[i - 1], to(cost, i - 2) + cost[i - 2])
    return memo[i]!!
}

// Bottom-Up DP
fun minCostClimbingStairs(cost: IntArray): Int {
    val n = cost.size
    val dp = IntArray(n + 1)
    dp[0] = 0
    dp[1] = 0
    for (i in 2..n) {
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
    }
    return dp[n]
}

// Space Optimization
fun minCostClimbingStairs(cost: IntArray): Int {
    if (cost.size == 2) return min(cost[0], cost[1])
    
    var result = 0
    var step2 = 0
    var step1 = 0
    for (i in 2..cost.size) {
        result = min(step1 + cost[i - 1], step2 + cost[i - 2])
        step2 = step1
        step1 = result
    }
    return result
}

From State

The from(i) / dp[i] represents the cost from i-th step:

• To 0 or 1 step cost cost[0] and cost[1].
• The cost from i-th step will be (the minimum of from(i - 2) and from(i - 1)) + cost[i].
• We calculate the minimum of from(i - 2) and from(i - 1) for the result.

// Top-Down Memoization
fun minCostClimbingStairs(cost: IntArray): Int {
    val n = cost.size
    if (n == 0) return cost[0]
    if (n == 1) return minOf(cost[0], cost[1])
    val memo = IntArray(n) { -1 }
    return minOf(
        from(cost, n - 1, memo),
        from(cost, n - 2, memo)
    )
}

private fun from(cost: IntArray, i: Int, memo: IntArray): Int {
    if (i <= 1) return cost[i]
    if (memo[i] != -1) return memo[i]
    memo[i] = cost[i] + minOf(
        from(cost, i - 1, memo),
        from(cost, i - 2, memo)
    )
    return memo[i]
}

// Bottom-Up Tabulation
// Time Complexity: O(n)
// Space Complexity: O(n)
fun minCostClimbingStairs(cost: IntArray): Int {
    val n = cost.size
    val dp = IntArray(n)
    dp[0] = cost[0]
    dp[1] = cost[1]
    for (i in 2 until n) {
        dp[i] = cost[i] + minOf(
            dp[i - 1], dp[i - 2]
        )
    }
    // To n-th step, we can either start from n - 1 or n - 2.
    return minOf(dp[n - 1], dp[n - 2])
}

// Space Optimization
// Time Complexity: O(n)
// Space Complexity: O(1)
fun from(cost: IntArray): Int {
    val n = cost.size
    // n - 1
    var n1 = cost[1]
    // n - 2
    var n2 = cost[0]
    
    var result = 0
    for (i in 2 until n) {
        // from(i) = cost(i) + min(from(i - 1), from(i - 2))
        result = cost[i] + minOf(n1, n2)
        n2 = n1
        n1 = result
    }
    return minOf(n2, n1)
}

def minCostClimbingStairs(self, cost: List[int]) -> int:
    n = len(cost)
    # dp[i] = the cost from i-th step
    dp = [cost[0], cost[1]] + [0] * (n - 2)
    for i in range(2, n):
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
    return min(dp[n - 1], dp[n - 2])

# Space Optimization
def minCostClimbingStairs(self, cost: List[int]) -> int:
    n = len(cost)
    # dp[i] = the cost from i-th step
    n1, n2 = cost[0], cost[1]
    for i in range(2, n):
        result = cost[i] + min(n1, n2)
        n1 = n2
        n2 = result
    return min(n1, n2)