Problem
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
Discussion
To solve this problem we use a dynamic programming approach. We create a zero-indexed array dp and a new zero-indexed array, newCosts. The newCosts array is created to make it easier to calculate the costs of every step.
We fill out the newCosts array from index 1 by taking the cost value of index-1.We fill out the first 2 values in the dp array. The first value is zero. The second value will be dp[0]+ newCosts[1]+1. The third value is the minimum of dp[1]+newCosts[2]+1 and dp[0] +newCosts[2]+4. We write code to return the value of dp[1] if the value of n is 1 and dp[2] if n's value is 2.
We iterate from the value of 3 to the end of the array calling the value i. We take the minimum of 3 values(dp[i-3]+newCosts[i]+(i-(i-3))^2,dp[i-2]+newCosts[i]+(i-(i-2))^2 and dp[i-1]+newCosts[i]+((i-(i-1))^2).After the iteration is finished,we return dp[n].
Solution
Java
class Solution {
public int climbStairs(int n, int[] costs) {
int [] dp=new int[n+1];
int [] newCosts=new int[costs.length+1];
for(int i=1;i<newCosts.length;i++){
newCosts[i]=costs[i-1];
}
dp[1]=newCosts[1]+1;
if(n==1)return dp[1];
dp[2]=Math.min(dp[1]+newCosts[2]+1,newCosts[2]+4);
if(n==2)return dp[2];
for(int i=3;i<=n;i++){
int costMinus3=dp[i-3]+newCosts[i]+((i-(i-3))*(i-(i-3)));
int costMinus2=dp[i-2]+newCosts[i]+((i-(i-2))*(i-(i-2)));
int costMinus1=dp[i-1]+newCosts[i]+((i-(i-1))*(i-(i-1)));
dp[i]=Math.min(costMinus1,Math.min(costMinus2,costMinus3));
}
return dp[n];
}
}
C#
public class Solution {
public int ClimbStairs(int n, int[] costs) {
int [] dp=new int[n+1];
int [] newCosts=new int[costs.Length+1];
for(int i=1;i<newCosts.Length;i++){
newCosts[i]=costs[i-1];
}
dp[1]=newCosts[1]+1;
if(n==1)return dp[1];
dp[2]=Math.Min(dp[1]+newCosts[2]+1,newCosts[2]+4);
if(n==2)return dp[2];
for(int i=3;i<=n;i++){
int costMinus3=dp[i-3]+newCosts[i]+((i-(i-3))*(i-(i-3)));
int costMinus2=dp[i-2]+newCosts[i]+((i-(i-2))*(i-(i-2)));
int costMinus1=dp[i-1]+newCosts[i]+((i-(i-1))*(i-(i-1)));
dp[i]=Math.Min(costMinus1,Math.Min(costMinus2,costMinus3));
}
return dp[n];
}
}
Top comments (0)