grid47 Exploring patterns and algorithms
Aug 24, 2024
4 min read
Solution to LeetCode 746: Min Cost Climbing Stairs Problem
You are climbing a staircase with a cost associated with each step. You can either start at the first or second step. At each step, you can either move one step or skip one step. Find the minimum cost to reach the top of the staircase.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array `cost`, where `cost[i]` is the cost of the ith step.
Example: cost = [5, 10, 15, 20]
Constraints:
• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999
Output: Return the minimum cost to reach the top of the staircase.
Example: For cost = [5, 10, 15, 20], the output is 15.
Constraints:
Goal: To minimize the cost, choose whether to move one step or skip one step depending on the given costs.
Steps:
• Use dynamic programming to calculate the minimum cost of reaching each step.
• For each step, you can either come from the previous step or skip one step, and choose the minimum cost.
Goal: The array `cost` has at least two elements, and each element is a non-negative integer.
Steps:
• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999
Assumptions:
• There will always be at least two steps in the staircase.
• Input: For cost = [5, 10, 15, 20]
• Explanation: Starting at step 1 with cost 10, and skipping to step 3 with cost 15. Total cost: 10 + 15 = 15.
• Input: For cost = [1, 20, 10, 5, 30, 10]
• Explanation: Starting at step 0 with cost 1, skipping steps, and reaching the top with a total cost of 16.
Approach: Use dynamic programming to calculate the minimum cost of reaching each step by considering the previous step and the step before it.
Observations:
• The problem is similar to the Fibonacci sequence but with costs associated with each step.
• Dynamic programming allows us to break down the problem and calculate the optimal cost to reach the top step.
Steps:
• Create an array `dp` where `dp[i]` represents the minimum cost to reach step `i`.
• Initialize `dp[0] = cost[0]` and `dp[1] = cost[1]`.
• Iterate through the array and calculate `dp[i] = min(dp[i-1] + cost[i], dp[i-2] + cost[i])`.
• Return the value `dp[n]` where `n` is the last step.
Empty Inputs:
• The problem guarantees that `cost.length` will be at least 2, so empty inputs are not possible.
Large Inputs:
• The solution should efficiently handle input sizes up to 1000 steps.
Special Values:
• If all costs are the same, the minimum cost will be the same regardless of the steps taken.
Constraints:
• The solution should work within the provided constraints for both time and space efficiency.
intminCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n +1, 0);
for(int i =2; i <= n; i++)
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
return dp[n];
}
1 : Function Definition
intminCostClimbingStairs(vector<int>& cost) {
This line defines the function minCostClimbingStairs that takes a vector of integers (cost) as input and returns an integer representing the minimum cost to reach the top.
2 : Variable Initialization
int n = cost.size();
The variable 'n' is initialized to the size of the 'cost' vector, representing the number of steps in the staircase.
3 : DP Array Initialization
vector<int> dp(n +1, 0);
Initialize a dynamic programming (DP) array 'dp' of size n+1, with all elements set to 0. This array will store the minimum cost to reach each step.
4 : For Loop
for(int i =2; i <= n; i++)
Start of the for loop, which iterates from step 2 to step n, calculating the minimum cost for each step.
At each step, the cost to reach step 'i' is calculated by taking the minimum of the cost to reach step 'i-1' and step 'i-2' plus the respective step costs from the 'cost' array.
6 : Return Statement
return dp[n];
Return the minimum cost to reach the top of the staircase, which is stored in dp[n].
Best Case: O(n), where n is the length of the `cost` array.
Average Case: O(n), where n is the length of the `cost` array.
Worst Case: O(n), where n is the length of the `cost` array.
Description: The time complexity is O(n) because we iterate over the `cost` array once.
Best Case: O(n), the space complexity remains the same for all cases.
Worst Case: O(n), because we use an array `dp` to store the minimum cost at each step.
Description: The space complexity is O(n) because we need an additional array to store the minimum costs.
