The example problem
You are climbing a staircase with n steps. Each move you climb either 1 or 2 steps. In how many different ways can you reach the top?
Input: n = 6 Output: 13
Picture it
Picture the staircase with a number written on each step: the number of different ways to stand on that step. Your last move onto step i came either from step i − 1 (a 1-step) or from step i − 2 (a 2-step). So the ways to reach step i are the two numbers below it added together. We fill the steps from the bottom up.
The key idea
ways[i] = ways[i − 1] + ways[i − 2]: the Fibonacci pattern. Only the last two numbers are needed. O(n).
Python
def climb(n):
ways = [1, 1] + [0] * (n - 1)
for i in range(2, n + 1):
ways[i] = ways[i - 1] + ways[i - 2]
return ways[n]Practise recursion · dp
- LeetCode 53Maximum Subarray (Kadane)The best winning streak in a trading diary
- LeetCode 118Pascal’s TriangleStacking oranges in a triangle
- LeetCode 120TriangleThe cheapest way down a hill
- LeetCode 139Word BreakSnapping word tiles onto a sentence strip
- LeetCode 279Perfect SquaresBuilding a number from square tiles
- LeetCode 1137N-th Tribonacci NumberA staircase with 1, 2 or 3-step jumps
NeetCode 150 problems that use it
1-D DP · 2-D DP · Backtracking ·
- LeetCode 78 · MediumSubsetsPizza toppings: take it or leave it
- LeetCode 39 · MediumCombination SumFilling a piggy bank with reusable coins
- LeetCode 46 · MediumPermutationsEvery way to seat guests in a row of chairs
- LeetCode 90 · MediumSubsets IIToppings with duplicates, no repeated pizzas
- LeetCode 40 · MediumCombination Sum IIEach coin used once, no repeated handfuls
- LeetCode 79 · MediumWord SearchTracing a word through a letter grid
- LeetCode 131 · MediumPalindrome PartitioningCutting a ribbon only at mirror points
- LeetCode 17 · MediumLetter Combinations of a Phone NumberTyping on an old phone keypad
- LeetCode 51 · HardN-QueensPlacing queens that can’t attack each other
- LeetCode 70 · EasyClimbing StairsCounting ways up a staircase
- LeetCode 746 · EasyMin Cost Climbing StairsA staircase with a toll on every step
- LeetCode 198 · MediumHouse RobberA burglar who can’t hit two neighbours
- LeetCode 213 · MediumHouse Robber IIHouses around a roundabout
- LeetCode 5 · MediumLongest Palindromic SubstringA mirror sliding along the letters
- LeetCode 647 · MediumPalindromic SubstringsCounting every mirror image hidden in a word
- LeetCode 91 · MediumDecode WaysHow many ways to read a secret number code
- LeetCode 322 · MediumCoin ChangeFewest coins when greedy fails
- LeetCode 152 · MediumMaximum Product SubarrayMultipliers where a minus sign flips everything
- LeetCode 139 · MediumWord BreakSnapping word tiles onto a sentence strip
- LeetCode 300 · MediumLongest Increasing SubsequenceDealing cards into patience piles
- LeetCode 416 · MediumPartition Equal Subset SumCan a pile of weights balance on a scale?
- LeetCode 62 · MediumUnique PathsA delivery robot that only goes right or down
- LeetCode 1143 · MediumLongest Common SubsequenceMatching two DNA strands
- LeetCode 309 · MediumBest Time to Buy and Sell Stock with CooldownA trader with three moods: holding, just sold, resting
- LeetCode 518 · MediumCoin Change IICounting the ways to make change
- LeetCode 494 · MediumTarget SumPlus or minus: walking a number line
- LeetCode 97 · MediumInterleaving StringBraiding two ribbons into one
- LeetCode 329 · HardLongest Increasing Path in a MatrixThe longest uphill hike on a terrain map
- LeetCode 115 · HardDistinct SubsequencesHow many ways to cross out letters and leave a word
- LeetCode 72 · MediumEdit DistanceFewest keystrokes to fix a typo
- LeetCode 312 · HardBurst BalloonsChoosing which balloon pops last
- LeetCode 10 · HardRegular Expression MatchingA stencil with wildcards and repeats