DFS + DP

851. Loud and Rich

Naive DFS got TLE

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        graph = collections.defaultdict(list)
        for a,b in richer:
            graph[b].append(a)
        #print(graph)
        def dfs(i):
            #print(i)
            res_q, res_i = quiet[i], i
            # please deep copy
            open_list = graph[i][:]
            while open_list:
                j = open_list.pop()
                #print(j, quiet[j])
                if quiet[j]<res_q:
                    res_i=j
                    res_q = quiet[j]
                #res = min(res, quiet[j])
                #print(graph[j])
                open_list +=graph[j]
                #print(open_list)
            return res_i
        return [dfs(i) for i in range(len(quiet))]

DP got AC

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        graph = collections.defaultdict(list)
        for a,b in richer:
            graph[b].append(a)
        from functools import lru_cache
        @lru_cache(None)
        def dfs(i):
            res = [quiet[i], i]
            if not graph[i]:return res
            fin_res =[res] + [dfs(j) for j in graph[i]]
            return min(fin_res)
        return [dfs(i)[1] for i in range(len(quiet))]