DP

1565t Modern Ludo I

There is a one-dimensional board with a starting point on the far left side of the board and an end point on the far right side of the board. There are several positions on the board that are connected to other positions, ie if A is connected to B, then when chess falls at position A, you can choose whether to move the chess from A to B. And the connection is one way, which means that the chess cannot move from B to A. Now given the length and connections of the board, and you have a six-sided dice(1-6), output the minimum steps to reach the end point.

Example1

Input: length = 10 and connections = [[2, 10]]
Output: 1
Explanation: 
1->2 (dice)
2->10(for free)

"""
有可能有兩多個connecting points
"""
def modernLudo(self, length, connections):
    dist = [float('inf')] * (length+1)
    route = defaultdict(set)
    for con in connections:
        route[con[0]].add(con[1])
    q = [1]
    dist[1] = 0
    
    while q:
        d = q.pop(0)
        for step in range(1,7):
            next = d+step
            if next < length and dist[next] > dist[d] + 1:
                dist[next] = dist[d]+1
                q.append(next)
                
        if d in route:
            for next in route[d]:
                if dist[next] > dist[d]:
                    dist[next] = dist[d]
                    q.append(next)
                    
    return dist[-1]

801 Minimum Swap To Make Sequence Increasing

Given A and B, return the minimum number of swaps to make both sequences strictly increasing.

Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1

"""
In min swap in ith index comes from in i-1 no swap or i-1 swap
n1, s1: no swap and swap
"""
def minSwap(self, A: List[int], B: List[int]) -> int:
    n1, s1 = 0, 1
    for i in range(1, len(A)):
        n2 = s2 = float("inf")
        if A[i-1] < A[i] and B[i-1] < B[i]:
            n2 = n1  # both no swap
            s2 = s1 + 1  # both swap
        if A[i-1] < B[i] and B[i-1] < A[i]:
            n2 = min(n2, s1) # i-1 swap
            s2 = n1 + 1 # i swap

        n1, s1 = n2, s2

    return min(n1, s1)

832. Binary Trees With Factors

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node's value should be equal to the product of the values of it's children.

How many binary trees can we make?

Input: A = [2, 4, 5, 10]
Output: 7
[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

"""
dp[i] = dp[j] * dp[k]   j < k < i
Use a hash to record k's index
"""
def numFactoredBinaryTrees(self, A: List[int]) -> int:
    n = len(A)
    A.sort()
    record = {x:i for i, x in enumerate(A)}
    dp = [1] * n
    
    for i, x in enumerate(A):
        for j in range(i):
            if x % A[j] == 0:
                y = x / A[j]
                if y in record:
                    dp[i] += dp[j] * dp[record[y]]
                    
    return sum(dp) % (10**9 +7)