1
class Solution:
2
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
3
        n = len(costs)
4
        m = n // 2
5

6
        @lru_cache(None)
7
        def dfs(cur, a):
8
            # cur is the current user index
9
            # `a` is the number of people travel to city `a`
10

11
            if cur == n:
12
                return 0
13

14
            # people to b city
15
            b = cur - a
16
            ans = float("inf")
17

18
            # the number of people to `a` city number did not reach to limit,
19
            # then current user can trval to city `a`
20

21
            if a < m:
22
                ans = min(dfs(cur + 1, a + 1) + costs[cur][0], ans)
23

24
            # the number of people to `b` city number did not reach to limit
25
            # then current user can trval to city `b`
26
            if b < m:
27
                ans = min(dfs(cur + 1, a) + costs[cur][1], ans)
28

29
            return ans
30

31
        return dfs(0, 0)