Advanced Patterns

1function MIS(u, parent):
2  take = 1
3  notake = 0
4  for v in adj[u]:
5    if v == parent: continue
6    notake += max(MIS(v, u).take, MIS(v, u).notake)
7    take += MIS(v, u).notake
8  return {take, notake}

1function TSP(dist):
2  n = len(dist)
3  dp = array(1<<n, n, +INF)
4  dp[1][0] = 0
5  for mask in 1..(1<<n)-1:
6    for i in 0..n-1:
7      if not (mask & (1<<i)): continue
8      for j in 0..n-1:
9        if mask & (1<<j): continue
10        dp[mask | (1<<j)][j] = min(dp[mask | (1<<j)][j], dp[mask][i] + dist[i][j])
11  ans = +INF
12  for i in 0..n-1:
13    ans = min(ans, dp[(1<<n)-1][i] + dist[i][0])
14  return ans

1function count(N):
2  digits = toDigits(N)
3  memo = {}
4  function dfs(pos, tight, sum):
5    if pos == len(digits): return condition(sum)
6    key = (pos, tight, sum)
7    if key in memo: return memo[key]
8    limit = digits[pos] if tight else 9
9    ans = 0
10    for d in 0..limit:
11      ans += dfs(pos+1, tight && d==limit, sum + d)
12    memo[key] = ans
13    return ans
14  return dfs(0, true, 0)