SeaCode

Appearance

Climbing Stairs ​

Problem Description ​

Given an integer array A of length N. Where Ai is the cost of stepping on the ith stair.

From ith stair, you can go to i+1th or i+2th numbered stair.

Initially, you are at 1st stair find the minimum cost to reach Nth stair.

Problem Constraints

2 <= N <= 10^5
1 <= Ai <= 10^4
2 <= N <= 10^5
1 <= Ai <= 10^4

Input Format

The first and only argument is an integer array A.
The first and only argument is an integer array A.

Output Format

Return an integer.
Return an integer.

Example Input

Input 1:
A = [1, 2, 1, 3]

Input 2:
A = [1, 2, 3, 4]
Input 1:
A = [1, 2, 1, 3]

Input 2:
A = [1, 2, 3, 4]

Example Output

Output 1:
5

Output 2:
7
Output 1:
5

Output 2:
7

Example Explanation

Explanation 1:
1 -> 3 -> 4

Explanation 2:
1 -> 2 -> 4
Explanation 1:
1 -> 3 -> 4

Explanation 2:
1 -> 2 -> 4

Solution ​

swift
import Foundation

class Solution {
	func solve(_ A: inout [Int]) -> Int {
        let len = A.count
        if len == 0 {
            return 0
        }
        if len == 1 {
            return A[len-1]
        }
        if len == 2 {
            return A[len-2] + A[len-1]
        }
        var ret = Array(repeating:0, count:len)
        ret[len-1] = A[len-1]
        ret[len-2] = A[len-2] + A[len-1]
        
        for i in (0..<len-2).reversed() {
            ret[i] = A[i] + min(ret[i+1],ret[i+2])
        }
        return ret[0]
	}
}
import Foundation

class Solution {
	func solve(_ A: inout [Int]) -> Int {
        let len = A.count
        if len == 0 {
            return 0
        }
        if len == 1 {
            return A[len-1]
        }
        if len == 2 {
            return A[len-2] + A[len-1]
        }
        var ret = Array(repeating:0, count:len)
        ret[len-1] = A[len-1]
        ret[len-2] = A[len-2] + A[len-1]
        
        for i in (0..<len-2).reversed() {
            ret[i] = A[i] + min(ret[i+1],ret[i+2])
        }
        return ret[0]
	}
}

References ​