Welcome to Subscribe On Youtube

3693. Climbing Stairs II

Description

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 <= 105​​​​​​​
  • 1 <= costs[i] <= 104

Solutions

Solution 1

  • class Solution {
    public int climbStairs(int n, int[] costs) {
        int[] f = new int[n + 1];
        final int inf = Integer.MAX_VALUE / 2;
        Arrays.fill(f, inf);
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int x = costs[i - 1];
            for (int j = Math.max(0, i - 3); j < i; ++j) {
                f[i] = Math.min(f[i], f[j] + x + (i - j) * (i - j));
            }
        }
        return f[n];
    }
}


  • class Solution {
public:
    int climbStairs(int n, vector<int>& costs) {
        vector<int> f(n + 1, INT_MAX / 2);
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int x = costs[i - 1];
            for (int j = max(0, i - 3); j < i; ++j) {
                f[i] = min(f[i], f[j] + x + (i - j) * (i - j));
            }
        }
        return f[n];
    }
};


  • class Solution:
    def climbStairs(self, n: int, costs: List[int]) -> int:
        n = len(costs)
        f = [inf] * (n + 1)
        f[0] = 0
        for i, x in enumerate(costs, 1):
            for j in range(i - 3, i):
                if j >= 0:
                    f[i] = min(f[i], f[j] + x + (i - j) ** 2)
        return f[n]


  • func climbStairs(n int, costs []int) int {
	const inf = int(1e9)
	f := make([]int, n+1)
	for i := range f {
		f[i] = inf
	}
	f[0] = 0
	for i := 1; i <= n; i++ {
		x := costs[i-1]
		for j := max(0, i-3); j < i; j++ {
			f[i] = min(f[i], f[j]+x+(i-j)*(i-j))
		}
	}
	return f[n]
}


  • function climbStairs(n: number, costs: number[]): number {
    const inf = Number.MAX_SAFE_INTEGER / 2;
    const f = Array(n + 1).fill(inf);
    f[0] = 0;

    for (let i = 1; i <= n; ++i) {
        const x = costs[i - 1];
        for (let j = Math.max(0, i - 3); j < i; ++j) {
            f[i] = Math.min(f[i], f[j] + x + (i - j) * (i - j));
        }
    }
    return f[n];
}


  • impl Solution {
    pub fn climb_stairs(n: i32, costs: Vec<i32>) -> i32 {
        let n = n as usize;
        let inf = i32::MAX / 2;
        let mut f = vec![inf; n + 1];
        f[0] = 0;
        for i in 1..=n {
            let x = costs[i - 1];
            for j in (i.saturating_sub(3))..i {
                f[i] = f[i].min(f[j] + x + ((i - j) * (i - j)) as i32);
            }
        }
        f[n]
    }
}

All Problems

All Solutions