LeetCode in Kotlin
3693. Climbing Stairs II
Medium
You are climbing a staircase with n + 1 steps, numbered from 0 to n.
You are also given a 1-indexed integer array costs of length n, where costs[i] is the cost of step i.
From step i, you can jump only to step i + 1, i + 2, or i + 3. The cost of jumping from step i to step j is defined as: costs[j] + (j - i)2
You start from step 0 with cost = 0.
Return the minimum total cost to reach step n.
Example 1:
Input: n = 4, costs = [1,2,3,4]
Output: 13
Explanation:
One optimal path is 0 → 1 → 2 → 4
Jump
Cost Calculation
Cost
0 → 1
costs[1] + (1 - 0)2 = 1 + 1
2
1 → 2
costs[2] + (2 - 1)2 = 2 + 1
3
2 → 4
costs[4] + (4 - 2)2 = 4 + 4
8
Thus, the minimum total cost is 2 + 3 + 8 = 13
Example 2:
Input: n = 4, costs = [5,1,6,2]
Output: 11
Explanation:
One optimal path is 0 → 2 → 4
Jump
Cost Calculation
Cost
0 → 2
costs[2] + (2 - 0)2 = 1 + 4
5
2 → 4
costs[4] + (4 - 2)2 = 2 + 4
6
Thus, the minimum total cost is 5 + 6 = 11
Example 3:
Input: n = 3, costs = [9,8,3]
Output: 12
Explanation:
The optimal path is 0 → 3 with total cost = costs[3] + (3 - 0)2 = 3 + 9 = 12
Constraints:
1 <= n == costs.length <= 1051 <= costs[i] <= 104
Solution
import kotlin.math.min
@Suppress("unused")
class Solution {
fun climbStairs(n: Int, costs: IntArray): Int {
if (costs.size == 1) {
return costs[0] + 1
}
var one = costs[0] + 1
var two = min(one + costs[1] + 1, costs[1] + 4)
if (costs.size < 3) {
return two
}
var three = min(one + costs[2] + 4, min(two + costs[2] + 1, costs[2] + 9))
if (costs.size < 4) {
return three
}
for (i in 3..<costs.size) {
val four =
(
min(
three + costs[i] + 1,
min(two + costs[i] + 4, one + costs[i] + 9),
)
)
one = two
two = three
three = four
}
return three
}
}