746. 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]`

解法解析

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

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

Bottom-Up Dynamic Programming (Tabulation)

Top-Down Dynamic Programming (Recursion + Memoization)

Bottom-Up, Constant Space

解法範例

Go

Bottom-Up Dynamic Programming (Tabulation)
``````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)
``````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
``````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)
``````/**
* @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)
``````/**
* @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
``````/**
* @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)
``````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)
``````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
``````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)
``````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)
``````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
``````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)
``````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)
``````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
``````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

``````
``````

Swift

Bottom-Up Dynamic Programming (Tabulation)
``````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)
``````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
``````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
}
}
``````