A. Calculate Amount Paid in Taxes (opens new window)

Start from the smallest upper bound, if our income is more than the previous upper bound, we have to pay tax for the amount within the range made by the previous upper bound and current upper bound.

For the first upper bound, we dont have a previous upper bound, thus just pay the tax within the range made by 0 and this upper bound.

DETAILS

def calculateTax(self, A: List[List[int]], income: int) -> float:
        n, res = len(A), A[0][0] * A[0][1] / 100
        if income <= A[0][0]: return income *A[0][1] / 100
        for i in range(1, n):
            if income >= A[i - 1][0]:
                res += A[i][1]*(min(income,A[i][0]) - A[i - 1][0]) / 100
            else:
                break
        return res

B. Minimum Path Cost in a Grid (opens new window)

Quite straght-forward DP, we just need to update the minimum cost of reaching cell[i][j] using all the pathes that end by it.

DETAILS

def minPathCost(self, G: List[List[int]], C: List[List[int]]) -> int:
        m, n, base = len(G), len(G[0]), 10 ** 9 
        DP = [[base] * n for _ in range(m)]
        for i in range(n): 
            DP[0][i] = G[0][i]
        for r in range(m - 1):
            for c in range(n):
                for cc in range(n):
                    DP[r + 1][cc] = min(G[r + 1][cc] + DP[r][c] + C[G[r][c]][cc], DP[r + 1][cc])
        return min(DP[m - 1])

C. Fair Distribution of Cookies (opens new window)

DETAILS

def distributeCookies(self, cookies: List[int], k: int) -> int:
        def solve(A):
            cc = [0] * n
            for i, a in enumerate(A): cc[a] += cookies[i]
            return max(cc)
        cookies.sort()
        n, res = len(cookies), 10 ** 9 + 7
        if len(cookies)==k: return max(cookies)      
        for i in itertools.product(list(range(k)), repeat=n): res=min(res, solve(i))
        return res

D. Naming a Company (opens new window)

Please refer to This LC Discussion (opens new window) for my solutions in English.

看一下下面这个例子，我们把单词按照首字母来分类，显然，我们只能交换不同首字母的两个词（否则交换之后必定还是之前的两个词）。

因为"offee"这个后缀在两个集合中都出现了，那么无论是"coffee" "boffee"肯定都是不能拿来交换的，我们只能在剩下的词（后缀唯一的词）中选择。

两边各有2个后缀唯一的词，交叉下来一共有4中搭配方案，考虑到我们可以交换两个词顺序，一共就是8钟可能的方案。

这样一来我们只需要遍历所有可能的【首字母对】，比如【ab】，【ac】，【xy】，找每个首字母对里一共可以有多少种方案，把所有数量加在一起即可。

DETAILS

def distinctNames(self, ideas: List[str]) -> int:
        # Group strings by their initials
        A = [set() for _ in range(26)]
        for idea in ideas:
            A[ord(idea[0]) - ord('a')].add(idea[1:])
        
        ans = 0
        # Calculate number of valid names from every initial pair.
        for i in range(25):
            for j in range(i + 1, 26):
                k = len(A[i] & A[j]) # Number of duplicated suffixes
                ans += 2 * (len(A[i]) - k) * (len(A[j]) - k)
        return ans