3693. Climbing Stairs II

/**
 * Problem: LeetCode 3693 - Climbing Stairs II
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int climbStairs(int n, int[] costs) {
        int[] dp = new int[n + 1];
        dp[0] = 0; // Base case: start at step 0 with cost 0

        for (int j = 1; j <= n; j++) {
            int best = Integer.MAX_VALUE;

            // Jump from j-1, j-2, or j-3 (only if valid step >= 0)
            for (int d = 1; d <= 3 && j - d >= 0; d++) {
                best = Math.min(best, dp[j - d] + costs[j - 1] + d * d);
            }

            dp[j] = best;
        }

        return dp[n];
    }
}

"""
Problem: LeetCode 3693 - Climbing Stairs II
Difficulty: Medium
Language: Python 3
Author: CodeByTushu
"""


class Solution:
    def climbStairs(self, n: int, costs: list[int]) -> int:
        dp = [0] * (n + 1)  # dp[j] = minimum cost to reach step j

        for j in range(1, n + 1):
            best = float("inf")
            # Evaluate backward jumps of size 1, 2, or 3
            for d in range(1, 4):
                if j - d >= 0:
                    cand = dp[j - d] + costs[j - 1] + d * d
                    if cand < best:
                        best = cand
            dp[j] = best

        return dp[n]

/**
 * Problem: LeetCode 3693 - Climbing Stairs II
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int climbStairs(int n, std::vector<int>& costs) {
        std::vector<int> dp(n + 1, 0);

        for (int j = 1; j <= n; ++j) {
            int best = INT_MAX;
            // Jump from j-1, j-2, or j-3 (only if valid step >= 0)
            for (int d = 1; d <= 3 && j - d >= 0; ++d) {
                best = std::min(best, dp[j - d] + costs[j - 1] + d * d);
            }
            dp[j] = best;
        }

        return dp[n];
    }
};

/**
 * Problem: LeetCode 3693 - Climbing Stairs II
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */

/**
 * @param {number} n
 * @param {number[]} costs
 * @return {number}
 */
var climbStairs = function(n, costs) {
    const dp = new Array(n + 1).fill(0);

    for (let j = 1; j <= n; j++) {
        let best = Infinity;
        // Jump from j-1, j-2, or j-3 (where valid step >= 0)
        for (let d = 1; d <= 3 && j - d >= 0; d++) {
            const cand = dp[j - d] + costs[j - 1] + d * d;
            if (cand < best) best = cand;
        }
        dp[j] = best;
    }

    return dp[n];
};