1D Dynamic Programming

Question 1

Climbing Stairs - you are asked to climb n steps. From any step you can choose to climb two steps or one step. How many ways are there to climb those n steps

Answer 1

So how do we break this down into subproblems?
Well at any given step, the number of solutions is the sum of the ways to reach the final step from the next step and from the step after that.

def climbStairs(self, n: int) -> int:
    one, two = 1, 1
    for _ in range(n-1):
        one, two = one + two, one
    return one

Question 2

Min Cost to climb stairs

Answer 2

BTW Climbing stairs means going one past the final element, so we can just append a 0 to the input list to represent that

So what are our base cases? Well at the last index (before the top) the cost is the cost of that index as well as the second to last index because you go one or two steps respectively at that given price point.
From there, we can just work our way backwards and increment the cost at any given index by the minimum of the cost one step ahead, and the cost two steps ahead.
Finally we return the min of the 0th index and 1st index.

Question 3

House Robber 1/2

Answer 3

We’ll keep a rolling track of the max that can be achieved by everything up to and considering the current house as well as everything up to but not considering the current house.
rob1, rob2 = 0, 0
for money in houses:
temp = max(rob1 + money, rob2)
rob1, rob2 = rob2, temp
return rob2

Notice that on a given iteration, rob1 is the max that can be gotten not including the previous house. That means you can freely add this house if its worth it. Finally after the last iteration, rob2 represents the max you can steal.