Imagine you have a magical notebook 📓✨. This notebook remembers answers to problems you’ve already solved so you don’t have to solve them again.
Let’s start with something simple: climbing stairs. Each time, you can either take 1 step or 2 steps. How many ways can you climb to the top if there are n stairs?
Magical Notebook to the Rescue!
Define the problem: To find the number of ways to reach the nth step.
Remember the simple problems: The number of ways to get to step 1 is 1, and to step 2 is 2.
Steps:
If you’re on step 1, there’s only one way to stay there.
If you’re on step 2, there are two ways: step 1 to step 2, or jump directly to step 2.
For step 3 and beyond, you can either come from the step right before it (n-1) or jump from the step two before it (n-2).
Let’s write this in code:
`def climbStairs(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
steps = [0] * (n + 1)
steps[1] = 1
steps[2] = 2
for i in range(3, n + 1):
steps[i] = steps[i - 1] + steps[i - 2]
return steps[n]
print(climbStairs(5)) # Output: 8`
Another example!
You are in a candy store, and there are different candies in a line. Each candy has a different amount of happiness points. You can’t take two candies next to each other, or you’ll get a tummy ache. How do you collect the most happiness?
Magical Notebook to the Rescue!
Define the problem: To find the maximum happiness you can collect without taking two candies next to each other.
Remember the simple problems: The happiness points for each candy.
Steps:
If you only have one candy, take it.
If you have two candies, take the one with more happiness.
For three or more candies:
Decide to take the current candy and add it to the best of skipping the next candy.
Or skip the current candy and take the best up to the previous candy.
Let’s write this in code:
def maxCandyHappiness(happiness):
n = len(happiness)
if n == 0:
return 0
elif n == 1:
return happiness[0]
elif n == 2:
return max(happiness[0], happiness[1])
else:
max_happiness = [0] * n
max_happiness[0] = happiness[0]
max_happiness[1] = max(happiness[0], happiness[1])
for i in range(2, n):
max_happiness[i] = max(max_happiness[i-1], happiness[i] + max_happiness[i-2])
return max(max_happiness)
happiness = [3, 2, 5, 10, 7]
print(maxCandyHappiness(happiness)) # Output: 15
Why Use Dynamic Programming?
It saves time! Instead of doing the same work over and over, your helper remembers the answers and by remembering small answers, your helper can find the best way to solve the big problem!
Hope this helps!
Here are 3 leetcode questions to get you comfortable with this concept. Let me know how it goes ☺️
Jump Game : https://leetcode.com/problems/jump-game/description/
Unique Paths: https://leetcode.com/problems/unique-paths/description/
Scramble Strings: https://leetcode.com/problems/scramble-string/description/
Follow me on Instagram : https://www.instagram.com/yourtechsiss/
Top comments (0)