CS Studies

You are given an integer n representing the number of steps to reach the top of a staircase. You can climb with either 1 or 2 steps at a time.

Return the number of distinct ways to climb to the top of the staircase.

Example 1:

Input: n = 2

Output: 2

Explanation:

1. 1 + 1 = 2

2. 2 = 2

Example 2:

Input: n = 3

Output: 3

Explanation:

1. 1 + 1 + 1 = 3

2. 1 + 2 = 3

3. 2 + 1 = 3

Constraints:

• 1 <= n <= 45

class Solution:
    def climbStairs(self, n: int) -> int:

        def find_ways(steps_climbed):
            # eventually the user will reach 
	    # or surpass the fifth step
            if steps_climbed > n:
                return 0
            elif steps_climbed == n:
                return 1
            
            return find_ways(steps_climbed + 1) + 
			find_ways(steps_climbed + 2)
            
        return find_ways(0)



        

House Robber

Medium

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a straight line, i.e. the ith house is the neighbor of the (i-1)th and (i+1)th house.

You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.

Return the maximum amount of money you can rob without alerting the police.

Example 1:

Input: nums = [1,1,3,3]

Output: 4

Explanation: nums[0] + nums[2] = 1 + 3 = 4.

Example 2:

Input: nums = [2,9,8,3,6]

Output: 16

Explanation: nums[0] + nums[2] + nums[4] = 2 + 8 + 6 = 16.

Constraints:

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 100

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

	# [rob1, rob2, n, n+1, ...]
        for num in nums:
            temp = max(num + rob1, rob2)
            rob1 = rob2
            rob2 = temp
        return rob2

House Robber II

Medium Topics Company Tags Hints

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbors.

You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.

Return the maximum amount of money you can rob without alerting the police.

Example 1:

Input: nums = [3,4,3]

Output: 4

Explanation: You cannot rob nums[0] + nums[2] = 6 because nums[0] and nums[2] are adjacent houses. The maximum you can rob is nums[1] = 4.

Example 2:

Input: nums = [2,9,8,3,6]

Output: 15

Explanation: You cannot rob nums[0] + nums[2] + nums[4] = 16 because nums[0] and nums[4] are adjacent houses. The maximum you can rob is nums[1] + nums[4] = 15.

Constraints:

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 200

class Solution:

    def rob(self, nums: List[int]) -> int:
        return max(nums[0], self.helper(nums[1:]),
                            self.helper(nums[:-1]))

    def helper(self, nums):
        rob1, rob2 = 0, 0

        for num in nums:
            newRob = max(rob1 + num, rob2)
            rob1 = rob2
            rob2 = newRob
        return rob2

( basically the same solution except you will call it wants without the first element and once without the last element . he will also check a list of just the first element in case you get past a list of one single value )

a

a