2. Min cost climbing stairs

 You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

Answer:

If we start with a brute-force approach, we can construct a decision tree where each node represents a step, and from each step, you can either take 1 step or 2 steps forward. By exploring every possible path in this tree, we can find all potential jump routes and determine the minimum total cost to reach the final step.

Since each step branches into two possibilities, the total number of recursive calls doubles at every level. Therefore, the time complexity of this brute-force solution is O(2ⁿ).

Brute Force: Decision Tree

Optimal Substructure:

Dynamic Programming (DP) leverages the optimal substructure property, meaning the solution to a problem can be built from solutions to its subproblems.

In a brute-force approach, many recursive calls are repeated multiple times. Dynamic Programming helps eliminate this redundancy by storing the results of these overlapping subproblems in a memoization structure (like an array or dictionary), instead of recalculating them each time.

Optimal sub-structure

For example, in the decision tree above, the route 2 → 3 (weight = 20) is computed more than once. By storing this result in an array, we can reuse it whenever needed.

By converting the recursive solution into a bottom-up DP approach, we reduce the time complexity from O(2ⁿ) to O(n)— at the cost of O(n) additional space.

From exponential to linear, that’s the power of Dynamic Programming!

Bottum-up Solution:

start from index 2

If you start from the last position of the cost array, there’s only one possible move - to stay at that position.

  • So, the minimum cost at the last index is simply the cost of that step, i.e., 20.

index 1

Starting at index 1

From index 1, you have two choices:

  1. Take 1 step → total cost = 15 (current step) + 20 (next step) = 35

  2. Take 2 steps → total cost = 15 (current step) + 0 (since you jump beyond the last step) = 15

The minimum of these two values is 15, which we store in the answer array.

start at index 0

Starting at index 0

From index 0, you again have two options:

  1. Take 1 step → total cost = 10 (current step) + 15 (cost from index 1) = 25

  2. Take 2 steps → total cost = 10 (current step) + 20 (cost from index 2) = 30

 The minimum of these values is 25, which we store in the answer array.

Final Step

The overall minimum cost to reach the top is:

min(ans[0],ans[1])=min(25,15)=15

Final Answer: 15


Python Code:


 


Comments

Post a Comment

Popular posts from this blog

1. Repeated DNA Sequences

Image
 T he  DNA sequence  is composed of a series of nucleotides abbreviated as  'A' ,  'C' ,  'G' , and  'T' For example,  "ACGAATTCCG"  is a  DNA sequence . When studying  DNA , it is useful to identify repeated sequences within the DNA. Given a string  s  that represents a  DNA sequence , return all the  10 -letter-long  sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in  any order .   Example 1: Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"] Ex ample 2: Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"]
Read more

Top K Elements

Image
  The  top k elements  pattern is an important technique in coding that helps us efficiently find a specific number of elements, known as  k, from a set of data. This is particularly useful when we’re tasked with identifying the largest, smallest, or most/least frequent elements within an unsorted collection. Which data structure can we use to solve such problems? A heap is the best data structure to keep track of the smallest or largest k  elements. With this pattern, we either use a max heap or a min heap to find the smallest or largest k elements, respectively, because they allow us to efficiently maintain a collection of elements ordered in a way that gives us quick access to the smallest (min heap) or largest (max heap) element. Algorithm Max Heap => Smallest k elements Min Heap => Largest k elements Top 3 largest numbers
Read more

1. Valid palindrome

Image
Algorithm: Initialize two pointers, left at the start and right at the end of the string. Iterate until the left pointer is before the right pointer, skipping non-alphanumeric characters for both pointers. Compare characters positioned at the left and right pointers in lowercase; if they differ, return FALSE. Move left forward and right backward to check the next pair of characters. If the traversal completes without mismatches, return TRUE indicating the string is a palindrome. valid palindrome
Read more