# LeetCode Solution, Easy, 746. Min Cost Climbing Stairs

# [746. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)

## 題目敘述

You are given an integer array `cost` where `cost[i]` is the cost of `ith` step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index `0`, or the step with index `1`.

Return _the minimum cost to reach the top of the floor_.

**Example 1:**

    Input: cost = [10,15,20]
    Output: 15
    Explanation: You will start at index 1.

    - Pay 15 and climb two steps to reach the top.
    The total cost is 15.

**Example 2:**

    Input: cost = [1,100,1,1,1,100,1,1,100,1]
    Output: 6
    Explanation: You will start at index 0.

    - Pay 1 and climb two steps to reach index 2.
    - Pay 1 and climb two steps to reach index 4.
    - Pay 1 and climb two steps to reach index 6.
    - Pay 1 and climb one step to reach index 7.
    - Pay 1 and climb two steps to reach index 9.
    - Pay 1 and climb one step to reach the top.
    The total cost is 6.

**Constraints:**

- `2 <= cost.length <= 1000`
- `0 <= cost[i] <= 999`

**Hint 1:**

Build an array `dp` where `dp[i]` is the minimum cost to climb to the top starting from the ith staircase.

**Hint 2:**

Assuming we have `n` staircase labeled from `0` to `n - 1` and assuming the top is `n`, then `dp[n] = 0`, marking that if you are at the top, the cost is `0`.

**Hint 3:**

Now, looping from `n - 1` to `0`, the `dp[i] = cost[i] + min(dp[i + 1], dp[i + 2])`. The answer will be the minimum of `dp[0]` and `dp[1]`

### 題目翻譯

會有一個整數陣列 `cost` 每個位置代表了爬到這一階樓梯要花費的費用，每次移動可以選擇要一階還是兩階。要找出到達最高層時，所需最少的的成本是多少。

## 解法解析

因為每一次操作的花費成本都是基於之前的操作結果為基礎來計算的，所以是一個典型的 Dynamic programming 的題目。所以當然的就基本上可以有種解法：Tabulation 和 Memoization。

Dynamic Programming 最主要的解法就是找出**小問題**，因為最後的答案都是基於前面的答案為基礎累積的，所以其實就是每次解出**小問題**的答案。所以回到最原本的問題，當然就是你要踏出一階還是兩階哪個成本最低。成為函示就是：

`minimumCost[i] = min(minimumCost[i - 1] + cost[i - 1], minimumCost[i - 2] + cost[i - 2])`

而以下的解法差別就只是在於怎麼處理每次的小問題，依照 Dynamic programming 的解法，基本上就是分為 Tabulation 和 Memoization 兩種方式。

**Bottom-Up Dynamic Programming (Tabulation)**

這個解法主要就是使用了遍歷的方式來處理

**Top-Down Dynamic Programming (Recursion + Memoization)**

這一種解決小問題的解法就是遞迴了

**Bottom-Up, Constant Space**

這個方式跟第一種解法類似，只是不再使用陣列儲存之前處理的結果，而是直接用一個變數紀錄最新的結果。

### 解法範例

#### Go

##### Bottom-Up Dynamic Programming (Tabulation)

```go
func minCostClimbingStairs(cost []int) int {
	var minimumCost []int = make([]int, len(cost)+1)
	for i := 0; i < len(cost); i++ {
		minimumCost[i] = 0
	}
	for i := 2; i <= len(cost); i++ {
		var takeOneStep int = minimumCost[i-1] + cost[i-1]
		var takeTwoStep int = minimumCost[i-2] + cost[i-2]
		if takeOneStep < takeTwoStep {
			minimumCost[i] = takeOneStep
		} else {
			minimumCost[i] = takeTwoStep
		}
	}
	return minimumCost[len(cost)]
}
```

##### Top-Down Dynamic Programming (Recursion + Memoization)

```go
func minCostClimbingStairs(cost []int) int {
	var memo map[int]int = make(map[int]int)
	return minimumCost(cost, memo, len(cost))
}

func minimumCost(cost []int, memo map[int]int, i int) int {
	if i <= 1 {
		return 0
	}

	if val, ok := memo[i]; ok {
		return val
	}

	var downOne int = minimumCost(cost, memo, i-1) + cost[i-1]
	var downTwo int = minimumCost(cost, memo, i-2) + cost[i-2]
	if downOne > downTwo {
		memo[i] = downTwo
	} else {
		memo[i] = downOne
	}
	return memo[i]
}
```

##### Bottom-Up, Constant Space

```go
func minCostClimbingStairs(cost []int) int {
	var downOne int = 0
	var downTwo int = 0
	for i := 2; i <= len(cost); i++ {
		var temp int = downOne
		if downOne+cost[i-1] < downTwo+cost[i-2] {
			downOne += cost[i-1]
		} else {
			downOne = downTwo + cost[i-2]
		}
		downTwo = temp
	}
	return downOne
}
```

#### JavaScript

##### Bottom-Up Dynamic Programming (Tabulation)

```javascript
/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
    const minimumCost = new Array(cost.length + 1).fill(0);
    for (let i = 2; i <= cost.length; i++) {
        minimumCost[i] = Math.min(minimumCost[i - 1] + cost[i - 1], minimumCost[i - 2] + cost[i - 2]);
    }
    return minimumCost[cost.length];
};
```

##### Top-Down Dynamic Programming (Recursion + Memoization)

```javascript
/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
    const memo = {};

    const minimumCost = (i) => {
        if (i <= 1) return 0;
        if (i in memo) return memo[i];
        return (memo[i] = Math.min(minimumCost(i - 1) + cost[i - 1], minimumCost(i - 2) + cost[i - 2]));
    };
    return minimumCost(cost.length);
};
```

##### Bottom-Up, Constant Space

```javascript
/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
    let downOne = 0,
        downTwo = 0;
    for (let i = 2; i <= cost.length; i++) {
        const down = Math.min(downOne + cost[i - 1], downTwo + cost[i - 2]);
        downTwo = downOne;
        downOne = down;
    }
    return downOne;
};
```

#### Kotlin

##### Bottom-Up Dynamic Programming (Tabulation)

```kotlin
class Solution {
    fun minCostClimbingStairs(cost: IntArray): Int {
        var minimumCost: IntArray = IntArray(cost.size + 1, { 0 })

        for (i in 2..cost.size) {
            minimumCost[i] =
                    Math.min(minimumCost[i - 1] + cost[i - 1], minimumCost[i - 2] + cost[i - 2])
        }
        return minimumCost[cost.size]
    }
}
```

##### Top-Down Dynamic Programming (Recursion + Memoization)

```kotlin
class Solution {
    fun minCostClimbingStairs(cost: IntArray): Int {
        val memo = mutableMapOf<Int, Int>()

        fun minimumCost(i: Int): Int {
            if (i <= 1) return 0
            if (i in memo) return memo[i]!!
            memo[i] = Math.min(minimumCost(i - 1) + cost[i - 1], minimumCost(i - 2) + cost[i - 2])
            return memo[i]!!
        }

        return minimumCost(i = cost.size)
    }
}
```

##### Bottom-Up, Constant Space

```kotlin
class Solution {
    fun minCostClimbingStairs(cost: IntArray): Int {
        var downOne: Int = 0
        var downTwo: Int = 0
        for (i in 2..cost.size) {
            val temp: Int = downOne
            downOne = Math.min(downOne + cost[i - 1], downTwo + cost[i - 2])
            downTwo = temp
        }
        return downOne
    }
}
```

#### PHP

##### Bottom-Up Dynamic Programming (Tabulation)

```php
class Solution
{

    /**
     * @param Integer[] $cost
     * @return Integer
     */
    function minCostClimbingStairs($cost)
    {
        $minimumCost = array_fill(0, count($cost) + 1, 0);
        for ($i = 2; $i <= count($cost); $i++) {
            $minimumCost[$i] = min($minimumCost[$i - 1] + $cost[$i - 1], $minimumCost[$i - 2] + $cost[$i - 2]);
        }
        return $minimumCost[count($cost)];
    }
}
```

##### Top-Down Dynamic Programming (Recursion + Memoization)

```php
class Solution
{

    /**
     * @param Integer[] $cost
     * @return Integer
     */
    function minCostClimbingStairs($cost)
    {
        $memo = [];
        return $this->minimumCost($cost, count($cost), $memo);
    }

    function minimumCost($cost, $i, $memo)
    {
        if ($i <= 1) {
            return 0;
        }
        if (isset($memo[$i])) {
            return $memo[$i];
        }
        $memo[$i] = min($this->minimumCost($cost, $i - 1, $memo) + $cost[$i - 1], $this->minimumCost($cost, $i - 2, $memo) + $cost[$i - 2]);
        return $memo[$i];
    }
}
```

##### Bottom-Up, Constant Space

```php
class Solution
{

    /**
     * @param Integer[] $cost
     * @return Integer
     */
    function minCostClimbingStairs($cost)
    {
        $downOne = 0;
        $downTwo = 0;
        for ($i = 2; $i <= count($cost); $i++) {
            $temp = $downOne;
            $downOne = min($downOne + $cost[$i - 1], $downTwo + $cost[$i - 2]);
            $downTwo = $temp;
        }
        return $downOne;
    }
}
```

#### Python

##### Bottom-Up Dynamic Programming (Tabulation)

```python
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        # The array's length should be 1 longer than the length of cost
        # This is because we can treat the "top floor" as a step to reach
        minimum_cost: list[int] = [0] * (len(cost) + 1)

        # Start iteration from step 2, since the minimum cost of reaching
        # step 0 and step 1 is 0
        for i in range(2, len(cost) + 1):
            take_one_step: int = minimum_cost[i - 1] + cost[i - 1]
            take_two_steps: int = minimum_cost[i - 2] + cost[i - 2]
            minimum_cost[i] = min(take_one_step, take_two_steps)

        # The final element in minimum_cost refers to the top floor
        return minimum_cost[-1]
```

##### Top-Down Dynamic Programming (Recursion + Memoization)

```python
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        def minimum_cost(i: int):
            # Base case, we are allowed to start at either step 0 or step 1
            if i <= 1:
                return 0

            # Check if we have already calculated minimum_cost(i)
            if i in memo:
                return memo[i]

            # If not, cache the result in our hash map and return it
            down_one: int = cost[i - 1] + minimum_cost(i - 1)
            down_two: int = cost[i - 2] + minimum_cost(i - 2)
            memo[i] = min(down_one, down_two)
            return memo[i]

        memo: dict[int, int] = {}
        return minimum_cost(len(cost))
```

##### Bottom-Up, Constant Space

```python
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        down_one = down_two = 0
        for i in range(2, len(cost) + 1):
            temp: int = down_one
            down_one = min(down_one + cost[i - 1], down_two + cost[i - 2])
            down_two = temp

        return down_one
```

#### Rust

```rust
```

#### Swift

##### Bottom-Up Dynamic Programming (Tabulation)

```swift
class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        var minimumCost: [Int] = Array(repeating: 0, count: cost.count + 1)
        for i in 2...cost.count {
            let takeOneStep: Int = minimumCost[i - 1] + cost[i - 1]
            let takeTwoSteps: Int = minimumCost[i - 2] + cost[i - 2]
            minimumCost[i] = min(takeOneStep, takeTwoSteps)
        }

        return minimumCost[cost.count]
    }
}
```

##### Top-Down Dynamic Programming (Recursion + Memoization)

```swift
class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        func minimumCost(_ i: Int) -> Int {
            guard i > 1 else {
                return 0
            }

            if let val = memo[i] {
                return val
            }

            let downOne: Int = minimumCost(i - 1) + cost[i - 1]
            let downTwo: Int = minimumCost(i - 2) + cost[i - 2]
            memo[i] = min(downOne, downTwo)
            return memo[i]!
        }

        var memo = [Int: Int]()
        return minimumCost(cost.count)
    }
}
```

##### Bottom-Up, Constant Space

```swift
class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        var downOne: Int = 0
        var downTwo: Int = 0
        for i in 2...cost.count {
            let temp: Int = downOne
            downOne = min(downOne + cost[i - 1], downTwo + cost[i - 2])
            downTwo = temp
        }
        return downOne
    }
}
```