1359. Count All Valid Pickup and Delivery Options - cocoder39/coco39_LC GitHub Wiki

1359. Count All Valid Pickup and Delivery Options

class Solution:
    def countOrders(self, n: int) -> int:
        cache = [[-1 for _ in range(n+1)] for _ in range(n+1)]
        return self.findWays(n, n, cache)
    
    
    def findWays(self, unpicked: int, undelivered: int, cache: List[int]) -> int:        
        MOD = 10**9 + 7
        
        if unpicked == 0 and undelivered == 0:
            return 1
        
        if unpicked < 0 or undelivered < 0 or unpicked > undelivered:
            return 0
        
        if cache[unpicked][undelivered] != -1:
            return cache[unpicked][undelivered]
                
        # unpicked <= undelivered -> we can pick any of unpicked orders
        cache[unpicked][undelivered] = unpicked * self.findWays(unpicked-1, undelivered, cache)
        cache[unpicked][undelivered] %= MOD
        
        cache[unpicked][undelivered] += (undelivered-unpicked) * self.findWays(unpicked, undelivered-1, cache)
        cache[unpicked][undelivered] %= MOD
        
        return cache[unpicked][undelivered]