Knowee
Questions
Features
Study Tools

Given an integer array A of length N. Where Ai is the cost of stepping on the ith stair.From ith stair, you can go to i+1th or i+2th numbered stair.Initially, you are at 1st stair find the minimum cost to reach Nth stair.Problem Constraints2 <= N <= 1051 <= Ai <= 104Input FormatThe first and only argument is an integer array A.Output FormatReturn an integer.Example InputInput 1:A = [1, 2, 1, 3]Input 2:A = [1, 2, 3, 4]Example OutputOutput 1:5Output 2:7Example ExplanationExplanation 1:1 -> 3 -> 4Explanation 2:1 -> 2 -> 4

Question

Given an integer array A of length N. Where Ai is the cost of stepping on the ith stair.From ith stair, you can go to i+1th or i+2th numbered stair.Initially, you are at 1st stair find the minimum cost to reach Nth stair.Problem Constraints2 <= N <= 1051 <= Ai <= 104Input FormatThe first and only argument is an integer array A.Output FormatReturn an integer.Example InputInput 1:A = [1, 2, 1, 3]Input 2:A = [1, 2, 3, 4]Example OutputOutput 1:5Output 2:7Example ExplanationExplanation 1:1 -> 3 -> 4Explanation 2:1 -> 2 -> 4

...expand
🧐 Not the exact question you are looking for?Go ask a question

Solution

This problem can be solved using dynamic programming. Here are the steps:

  1. Create a new array dp of size N to store the minimum cost to reach each stair. Initialize dp[0] and dp[1] with the cost of the first and second stair respectively, i.e., dp[0] = A[0] and dp[1] = A[1].

  2. For each stair from the third to the Nth (i.e., from i = 2 to N-1), calculate the minimum cost to reach that stair. This is the minimum of the cost to reach the previous stair plus the cost of the current stair, and the cost to reach the stair before the previous one plus the cost of the current stair. In other words, dp[i] = min(dp[i-1], dp[i-2]) + A[i].

  3. The minimum cost to reach the Nth stair is stored in dp[N-1].

Here is a Python code snippet that implements these steps:

def minCost(A):
    N = len(A)
    dp = [0]*N
    dp[0] = A[0]
    dp[1] = A[1]
    for i in range(2, N):
        dp[i] = min(dp[i-1], dp[i-2]) + A[i]
    return dp[N-1]

In the first example, the minimum cost to reach the 4th stair is 5 (1 -> 3 -> 4). In the second example, the minimum cost to reach the 4th stair is 7 (1 -> 2 -> 4).

This problem has been solved

Similar Questions

is currently standing at stair 0 and wants to reach exactly the stair numbered C.The programmer can climb either H steps or 1 step in one move. Find the minimum number of moves required by the programmer to reach exactly the stair C.Input FormatThe first line of input will contain a single integer T, denoting the number of test cases.Each test case consists of a single line of input containing two space separated integers C and H denoting the number of stair the programmer wants to reach and the number of stairs the programmer can climb in one move.Constraints1 <= T <= 5001 <= C, H <= 100Output FormatFor each test case, output the minimum number of moves required by the programmer to reach exactly the stair numbered C.Sample Input 044 28 33 42 1Sample Output 02432Sample Input 13374 30588 71305 309Sample Output 17018305

You are climbing a staircase. It takes n steps to reach the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?Input FormatInput from stdin will be processed as follows and passed to the function.The first line contains an integer n, the number of steps.Constraints0 <= n <= 1000Output FormatThe output is the number of waysSample Input 02Sample Output 02

Given an array A of size N, find the minimum cost to convert it to a ternary array B. A ternary array can only have 0 or 1 or 2. After conversion, ensure that A[i] != B[i]. The cost of converting A[i] to B[i] is | A[i] - B[i] |.Input FormatThe first line of input contains a single integer N - the size of the array and the second line contains array elements.Output FormatPrint the minimum cost to convert array A to B.Constraints1 <= N <= 10000-100000 <= A[i] <= 100000ExampleInput51 -1 2 0 5Output7ExplanationGiven A = {1, -1, 2, 0, 5} can be converted to B = {2, 0, 1, 1, 2}, with a cost of |1-2| + |-1-0| + |2-1| + |0-1| + |5-2| = 1 + 1 + 1 + 1 + 3 = 7.

You are given an array of integers nums of length n.The cost of an array is the value of its first element. For example, the cost of [1,2,3] is 1 while the cost of [3,4,1] is 3.You need to divide nums into 3 disjoint contiguous subarrays.Return the minimum possible sum of the cost of these subarrays.

You are given an integer array nums and two integers cost1 and cost2. You are allowed to perform either of the following operations any number of times:Choose an index i from nums and increase nums[i] by 1 for a cost of cost1.Choose two different indices i, j, from nums and increase nums[i] and nums[j] by 1 for a cost of cost2.Return the minimum cost required to make all elements in the array equal.Since the answer may be very large, return it modulo 109 + 7. Example 1:Input: nums = [4,1], cost1 = 5, cost2 = 2Output: 15Explanation:The following operations can be performed to make the values equal:Increase nums[1] by 1 for a cost of 5. nums becomes [4,2].Increase nums[1] by 1 for a cost of 5. nums becomes [4,3].Increase nums[1] by 1 for a cost of 5. nums becomes [4,4].The total cost is 15.Example 2:Input: nums = [2,3,3,3,5], cost1 = 2, cost2 = 1Output: 6Explanation:The following operations can be performed to make the values equal:Increase nums[0] and nums[1] by 1 for a cost of 1. nums becomes [3,4,3,3,5].Increase nums[0] and nums[2] by 1 for a cost of 1. nums becomes [4,4,4,3,5].Increase nums[0] and nums[3] by 1 for a cost of 1. nums becomes [5,4,4,4,5].Increase nums[1] and nums[2] by 1 for a cost of 1. nums becomes [5,5,5,4,5].Increase nums[3] by 1 for a cost of 2. nums becomes [5,5,5,5,5].The total cost is 6.Example 3:Input: nums = [3,5,3], cost1 = 1, cost2 = 3Output: 4Explanation:The following operations can be performed to make the values equal:Increase nums[0] by 1 for a cost of 1. nums becomes [4,5,3].Increase nums[0] by 1 for a cost of 1. nums becomes [5,5,3].Increase nums[2] by 1 for a cost of 1. nums becomes [5,5,4].Increase nums[2] by 1 for a cost of 1. nums becomes [5,5,5].The total cost is 4. Constraints:1 <= nums.length <= 1051 <= nums[i] <= 1061 <= cost1 <= 1061 <= cost2 <= 106

1/3

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.