Climbing Stairs

Problem Description

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

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

Initially, you are at 1^st stair find the minimum cost to reach N^th stair.

Problem Constraints

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

Input Format

The first and only argument is an integer array A.

Output Format

Return an integer.

Example Input

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

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

Example Output

Output 1:
5

Output 2:
7

Example Explanation

Explanation 1:
1 -> 3 -> 4

Explanation 2:
1 -> 2 -> 4

Solution

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

• Interviewbit > Climbing Stairs