#!/usr/bin/python
# -*- coding: UTF-8 -*-

from typing import List, Generator
import heapq


class Graph:
    def __init__(self, vertex_count: int) -> None:
        self.adj = [[] for _ in range(vertex_count)]

    def add_edge(self, s: int, t: int, w: int) -> None:
        edge = Edge(s, t, w)
        self.adj[s].append(edge)

    def __len__(self) -> int:
        return len(self.adj)


class Vertex:
    def __init__(self, v: int, dist: int) -> None:
        self.id = v
        self.dist = dist

    def __gt__(self, other) -> bool:
        return self.dist > other.dist

    def __repr__(self) -> str:
        return str((self.id, self.dist))


class Edge:
    def __init__(self, source: int, target: int, weight: int) -> None:
        self.s = source
        self.t = target
        self.w = weight


class VertexPriorityQueue:
    def __init__(self) -> None:
        self.vertices = []

    def get(self) -> Vertex:
        return heapq.heappop(self.vertices)

    def put(self, v: Vertex) -> None:
        self.vertices.append(v)
        self.update_priority()

    def empty(self) -> bool:
        return len(self.vertices) == 0

    def update_priority(self) -> None:
        heapq.heapify(self.vertices)

    def __repr__(self) -> str:
        return str(self.vertices)


def dijkstra(g: Graph, s: int, t: int) -> int:
    size = len(g)

    pq = VertexPriorityQueue()  # 节点队列
    in_queue = [False] * size   # 已入队标记
    vertices = [                # 需要随时更新离s的最短距离的节点列表
        Vertex(v, float('inf')) for v in range(size)
    ]
    predecessor = [-1] * size   # 先驱

    vertices[s].dist = 0
    pq.put(vertices[s])
    in_queue[s] = True

    while not pq.empty():
        v = pq.get()
        if v.id == t:
            break
        for edge in g.adj[v.id]:
            if v.dist + edge.w < vertices[edge.t].dist:
                # 当修改了pq中的元素的优先级后：
                # 1. 有入队操作：触发了pq的堆化，此后出队可以取到优先级最高的顶点
                # 2. 无入队操作：此后出队取到的顶点可能不是优先级最高的，会有bug
                # 为确保正确，需要手动更新一次
                vertices[edge.t].dist = v.dist + edge.w
                predecessor[edge.t] = v.id
                pq.update_priority()        # 更新堆结构
            if not in_queue[edge.t]:
                pq.put(vertices[edge.t])
                in_queue[edge.t] = True

    for n in print_path(s, t, predecessor):
        if n == t:
            print(t)
        else:
            print(n, end=' -> ')
    return vertices[t].dist


def print_path(s: int, t: int, p: List[int]) -> Generator[int, None, None]:
    if t == s:
        yield s
    else:
        yield from print_path(s, p[t], p)
        yield t


if __name__ == '__main__':
    g = Graph(6)
    g.add_edge(0, 1, 10)
    g.add_edge(0, 4, 15)
    g.add_edge(1, 2, 15)
    g.add_edge(1, 3, 2)
    g.add_edge(2, 5, 5)
    g.add_edge(3, 2, 1)
    g.add_edge(3, 5, 12)
    g.add_edge(4, 5, 10)
    print(dijkstra(g, 0, 5))

    # 下面这个用例可以暴露更新队列元素优先级的问题
    # g = Graph(4)
    # g.add_edge(0, 1, 18)
    # g.add_edge(0, 2, 3)
    # g.add_edge(2, 1, 1)
    # g.add_edge(1, 3, 5)
    # g.add_edge(2, 3, 8)
    # g.add_edge(0, 3, 15)
    # print(dijkstra(g, 0, 3))

from collections import deque
from itertools import filterfalse

class Graph:
    def __init__(self, num_vertices: int):
        self._num_vertices = num_vertices
        self._adjacency = [[] for _ in range(num_vertices)]
    
    def add_edge(self, s: int, t: int) -> None:
        self._adjacency[s].append(t)

    def tsort_by_kahn(self) -> None:
        in_degree = [0] * self._num_vertices
        for v in range(self._num_vertices):
            if len(self._adjacency[v]):
                for neighbour in self._adjacency[v]:
                    in_degree[neighbour] += 1
        q = deque(filterfalse(lambda x: in_degree[x], range(self._num_vertices)))
        while q:
            v = q.popleft()
            print(f"{v} -> ", end="")
            for neighbour in self._adjacency[v]:
                in_degree[neighbour] -= 1
                if not in_degree[neighbour]:
                    q.append(neighbour)
        print("\b\b\b   ")

    def tsort_by_dfs(self) -> None:
        inverse_adjacency = [[] for _ in range(self._num_vertices)]
        for v in range(self._num_vertices):
            if len(self._adjacency[v]):
                for neighbour in self._adjacency[v]:
                    inverse_adjacency[neighbour].append(v)
        visited = [False] * self._num_vertices

        def dfs(vertex: int) -> None:
            if len(inverse_adjacency[vertex]):
                for v in inverse_adjacency[vertex]:
                    if not visited[v]:
                        visited[v] = True
                        dfs(v)
            print(f"{vertex} -> ", end="")
        
        for v in range(self._num_vertices):
            if not visited[v]:
                visited[v] = True
                dfs(v)
        
        print("\b\b\b   ")


if __name__ == "__main__":

    dag = Graph(4)
    dag.add_edge(1, 0)
    dag.add_edge(2, 1)
    dag.add_edge(1, 3)
    dag.tsort_by_kahn()
    dag.tsort_by_dfs()

from typing import List
from itertools import accumulate

def min_dist(weights: List[List[int]]) -> int:
    """Find the minimum weight path from the weights matrix."""
    m, n = len(weights), len(weights[0])
    table = [[0] * n for _ in range(m)]
    # table[i][j] is the minimum distance (weight) when
    # there are i vertical moves and j horizontal moves
    # left.
    table[0] = list(accumulate(reversed(weights[-1])))
    for i, v in enumerate(accumulate(row[-1] for row in reversed(weights))):
        table[i][0] = v
    for i in range(1, m):
        for j in range(1, n):
            table[i][j] = weights[~i][~j] + min(table[i - 1][j], table[i][j - 1])
    return table[-1][-1]


def min_dist_recur(weights: List[List[int]]) -> int:
    m, n = len(weights), len(weights[0])
    table = [[0] * n for _ in range(m)]
    def min_dist_to(i: int, j: int) -> int:
        if i == j == 0: return weights[0][0]
        if table[i][j]: return table[i][j]
        min_left = float("inf") if j - 1 < 0 else min_dist_to(i, j - 1)
        min_up = float("inf") if i - 1 < 0 else min_dist_to(i - 1, j)
        return weights[i][j] + min(min_left, min_up)
    return min_dist_to(m - 1, n - 1)


if __name__ == "__main__":
    weights = [[1, 3, 5, 9], [2, 1, 3, 4], [5, 2, 6, 7], [6, 8, 4, 3]]
    print(min_dist(weights))
    print(min_dist_recur(weights))

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from typing import List


def coins_dp(values: List[int], target: int) -> int:
    # memo[i]表示target为i的时候，所需的最少硬币数
    memo = [0] * (target+1)
    # 0元的时候为0个
    memo[0] = 0

    for i in range(1, target+1):
        min_num = 999999
        # 对于values中的所有n
        # memo[i]为 min(memo[i-n1], memo[i-n2], ...) + 1
        for n in values:
            if i >= n:
                min_num = min(min_num, 1 + memo[i-n])
            else:   # values中的数值要从小到大排序
                break
        memo[i] = min_num

    # print(memo)
    return memo[-1]


min_num = 999999
def coins_backtracking(values: List[int], target: int, cur_value: int, coins_count: int):
    if cur_value == target:
        global min_num
        min_num = min(coins_count, min_num)
    else:
        for n in values:
            if cur_value + n <= target:
                coins_backtracking(values, target, cur_value+n, coins_count+1)


if __name__ == '__main__':
    values = [1, 3, 5]
    target = 23
    print(coins_dp(values, target))
    coins_backtracking(values, target, 0, 0)
    print(min_num)

def levenshtein_dp(s: str, t: str) -> int:
    m, n = len(s), len(t)
    table = [[0] * (n) for _ in range(m)]

    for i in range(n):
        if s[0] == t[i]:
            table[0][i] = i - 0
        elif i != 0:
            table[0][i] = table[0][i - 1] + 1
        else:
            table[0][i] = 1

    for i in range(m):
        if s[i] == t[0]:
            table[i][0] = i - 0
        elif i != 0:
            table[i][0] = table[i - 1][0] + 1
        else:
            table[i][0] = 1

    for i in range(1, m):
        for j in range(1, n):
            table[i][j] = min(1 + table[i - 1][j], 1 + table[i][j - 1], int(s[i] != t[j]) + table[i - 1][j - 1])

    print(table)
    return table[-1][-1]


def common_substring_dp(s: str, t: str) -> int:
    m, n = len(s), len(t)
    table = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            table[i][j] = max(table[i - 1][j], table[i][j - 1], int(s[i - 1] == t[j - 1]) + table[i - 1][j - 1])
    return table[-1][-1]


if __name__ == "__main__":
    s = "mitcmu"
    t = "mtacnu"

    print(levenshtein_dp(s, t))
    print(common_substring_dp(s, t))

    s = "kitten"
    t = "sitting"

    print(levenshtein_dp(s, t))
    print(common_substring_dp(s, t))

    s = "flaw"
    t = "lawn"

    print(levenshtein_dp(s, t))
    print(common_substring_dp(s, t))