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 <= 10000 <= 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)
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
}
}