LeetCode Weekly Contest 300

number_of_increasing_paths_in_a_grid.py

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = {}
        
        def dfs(r, c, previous_val):
            if r < 0 or r == rows or \
               c < 0 or c == cols or \
               grid[r][c] <= previous_val:
                return 0
            
            if (r, c) in dp:
                return dp[(r, c)]
            
            res = 1
            res += dfs(r + 1, c, grid[r][c])
            res += dfs(r - 1, c, grid[r][c])
            res += dfs(r, c + 1, grid[r][c])
            res += dfs(r, c - 1, grid[r][c])

            dp[(r, c)] = res
            return res
        
        for r in range(rows):
            for c in range(cols):
                dfs(r, c, -1)
        return sum(dp.values()) % (10**9 + 7)

number_of_people_aware_of_a_secret.py

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        states = {1: 1} # date_start: num_people_known
        current_date = delay
        while current_date <= n:
            new_person_known = 0
            person_forgets = {}
            for date_start, num_people_known in states.items():
                if current_date - date_start >= delay:
                    if current_date - date_start < forget:
                        new_person_known += num_people_known
                    else:
                        person_forgets[date_start] = num_people_known

            # Remove person
            for date in person_forgets.keys():
                states[date] -= person_forgets[date]
                if states[date] <= 0:
                    del states[date]

            # Add new person
            if new_person_known != 0:
                states[current_date] = new_person_known

            # print(f"After day {current_date}, {new_person_known} new people know the secret, {sum(person_forgets.values())} people forget the secret, {states}, ans is {sum(states.values())}")

            current_date += 1
        return sum(states.values()) % (10**9 + 7)