Fibonacci series

(REC: N -> 0) Fibonacci Series Extension

509. Fibonacci Number (Easy)

def fib(self, n: int) -> int:
    @lru_cache(maxsize=None)
    def recursion(i):
        if i <= 1:
            return i
        else:
            return recursion(i - 1) + recursion(i - 2)

    return recursion(n)

70. Climbing Stairs (Easy)

def climbStairs(self, n: int) -> int:
    @lru_cache(maxsize=None)
    def recursion(i):
        if i <= 2:
            return i
        else:
            return recursion(i - 1) + recursion(i - 2)

    return recursion(n)

1137. N-th Tribonacci Number (Easy)

def tribonacci(self, n: int) -> int:
    @lru_cache(maxsize=None)
    def recursion(i):
        if i == 0:
            return 0
        elif i <= 2:
            return 1
        else:
            return recursion(i - 1) + recursion(i - 2) + recursion(i - 3)

    return recursion(n)

Staircase (E)

Problem Statement

Given a stair with n steps, implement a method to count how many possible ways are there to reach the top of the staircase, given that, at every step you can either take 1 step, 2 steps, or 3 steps.

Example 1:

Number of stairs (n) : 3

Number of ways = 4

Explanation: Following are the four ways we can climb : {1, 1, 1}, {1, 2}, {2, 1}, {3}

Example 2:

Number of stairs (n) : 4

Number of ways = 7

Explanation: Following are the seven ways we can climb : {1, 1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {2, 2}, {1, 3}, {3, 1}

def count_ways(n):
    @lru_cache(maxsize=None)
    def recursion(i):
        if i <= 1:
            return 1
        elif i == 2:
            return 2
        else:
            return recursion(i - 1) + recursion(i - 2) + recursion(i - 3)

    return recursion(n)

Number factors (E)

Problem Statement

Given a number n, implement a method to count how many possible ways there are to express n as the sum of 1, 3, or 4.

Example 1:

n : 4

Number of ways = 4

Explanation: Following are the four ways we can express ‘n’ : {1, 1, 1, 1}, {1, 3}, {3, 1}, {4}

Example 2:

n : 5

Number of ways = 6

Explanation: Following are the six ways we can express ‘n’ : {1, 1, 1, 1, 1}, {1, 1, 3}, {1, 3, 1}, {3, 1, 1}, {1, 4}, {4, 1}

def count_ways(n):
    @lru_cache(maxsize=None)
    def recursion(i):
        if i <= 2:
            return 1
        elif i == 3:
            return 2
        else:
            return recursion(i - 1) + recursion(i - 3) + recursion(i - 4)

    return recursion(n)

(REC: N -> 0) Min/Max

746. Min Cost Climbing Stairs (Easy)

def minCostClimbingStairs(self, cost: List[int]) -> int:
    @lru_cache(maxsize=None)
    def recursion(i):
        if i <= 1:
            return 0
        else:
            one_step = cost[i - 1] + recursion(i - 1)
            two_steps = cost[i - 2] + recursion(i - 2)
            return min(one_step, two_steps)

    n = len(cost)
    return recursion(n)

Minimum jumps with fee (E)

Problem Statement

Given a staircase with n steps and an array of n numbers representing the fee that you have to pay if you take the step. Implement a method to calculate the minimum fee required to reach the top of the staircase (beyond the top-most step). At every step, you have an option to take either 1 step, 2 steps, or 3 steps. You should assume that you are standing at the first step.

Example 1:

Number of stairs (n) : 6

Fee: {1, 2, 5, 2, 1, 2}

Output: 3

Explanation: Starting from index ‘0’, we can reach the top through: 0->3->top The total fee we have to pay will be (1+2).

Example 2:

Number of stairs (n): 4

Fee: {2, 3, 4, 5}

Output: 5

Explanation: Starting from index ‘0’, we can reach the top through: 0->1->top The total fee we have to pay will be (2+3).

def find_min_fee(fee):
    @lru_cache(maxsize=None)
    def recursion(i):
        if i <= 3:
            return fee[0]
        else:
            one_step = fee[i - 1] + recursion(i - 1)
            two_steps = fee[i - 2] + recursion(i - 2)
            three_steps = fee[i - 3] + recursion(i - 3)
            return min(one_step, two_steps, three_steps)

    n = len(fee)
    return recursion(n)

198. House Robber (Medium)

Also

def rob(self, nums: List[int]) -> int:
    @lru_cache(maxsize=None)
    def recursion(i):
        if i < 0:
            return 0
        else:
            robbed = nums[i] + recursion(i - 2)
            not_robbed = recursion(i - 1)
            return max(robbed, not_robbed)

    n = len(nums)
    return recursion(n - 1)

213. House Robber II (Medium)

Solution

The rob_simple() function is same as the function rob() in simple version of this problem (198. House Robber (Medium))

def rob(self, nums: List[int]) -> int:
    if len(nums) == 0:
        return 0
    elif len(nums) == 1:
        return nums[0]
    else:
        return max(self.rob_simple(nums[1:]), self.rob_simple(nums[:-1]))

(REC: 0 -> N) Min/Max

Minimum jumps to reach the end (E)

Problem Statement

Given an array of positive numbers, where each element represents the max number of jumps that can be made forward from that element, write a program to find the minimum number of jumps needed to reach the end of the array (starting from the first element). If an element is 0, then we cannot move through that element.

Example 1:

Input = {2,1,1,1,4}

Output = 3

Explanation: Starting from index ‘0’, we can reach the last index through: 0->2->3->4

Example 2:

Input = {1,1,3,6,9,3,0,1,3}

Output = 4

Explanation: Starting from index ‘0’, we can reach the last index through: 0->1->2->3->8

def count_min_jumps(jumps):
    @lru_cache(maxsize=None)
    def recursion(i):
        if i == n - 1:
            return 0
        else:
            mini = sys.maxsize
            for j in range(1, min(jumps[i] + 1, n - i)):
                required = 1 + recursion(i + j)
                mini = min(mini, required)
            return mini

    n = len(jumps)
    return recursion(0)