Skip to content

Instantly share code, notes, and snippets.

@lamhoangtung

lamhoangtung/number_of_increasing_paths_in_a_grid.py

Created July 3, 2022 04:35
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save lamhoangtung/eae6ca6f7b9f356d16cc2a9f5d4cdda8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save lamhoangtung/eae6ca6f7b9f356d16cc2a9f5d4cdda8 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. lamhoangtung created this gist Jul 3, 2022.
    27 changes: 27 additions & 0 deletions number_of_increasing_paths_in_a_grid.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,27 @@
    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)
    28 changes: 28 additions & 0 deletions number_of_people_aware_of_a_secret.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,28 @@
    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)