← leetcode

Climbing Stairs II

· Medium

LeetCode problem 3693

just a generic dynamic programming question, where at each stage, dp[i], you calculate the minimum cost it takes to get to it from dp[i-1], dp[i-2] and dp[i-3] and repeat it for every value until you reach dp[n].

code link to code

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

        for (int i = 1; i < n+1; ++i) {
            for (int d = 1; d < 4; ++d) {
                if (i - d < 0) break;

                dp[i] = min(dp[i], dp[i-d] + costs[i-1] + (d*d));
            }
        }

        return dp.back();
    }
};

complexity link to complexity

  • Time: O(n)
  • Space: O(n)

time taken link to time taken

  • 7 minutes and 34 seconds