4041. Climbing Stairs Ii¶

4041. 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)²

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)² = 1 + 1`	2
1 → 2	`costs[2] + (2 - 1)² = 2 + 1`	3
2 → 4	`costs[4] + (4 - 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)² = 1 + 4`	5
2 → 4	`costs[4] + (4 - 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)² = 3 + 9 = 12

Constraints:

1 <= n == costs.length <= 10⁵
1 <= costs[i] <= 10⁴

Solution¶

class Solution {
    private int dp[];
    public int climbStairs(int n, int[] costs) {
        dp = new int[n + 1]; 
        Arrays.fill(dp, -1);
        return solve(0, costs);
    }
    private int solve(int idx, int cost[]) {
        if (idx == cost.length) 
            return 0;
        if (idx > cost.length)
            return Integer.MAX_VALUE;
        if (dp[idx] != -1)
            return dp[idx];
        int op1 = Integer.MAX_VALUE / 10, op2 = Integer.MAX_VALUE / 10, op3 = Integer.MAX_VALUE / 10;
        if (idx + 1 <= cost.length) {
           op1 = cost[idx] + 1 + solve(idx + 1, cost); 
        } 
        if (idx + 2 <= cost.length) {
            op2 = cost[idx + 1] + 4 + solve(idx + 2, cost);
        }
        if (idx + 3 <= cost.length) {
            op3 = cost[idx + 2] + 9 + solve(idx + 3, cost); 
        }
        return dp[idx] = Math.min(op1, Math.min(op2, op3));
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]