box-lin/algorithm

my notebook

leetcode-record

algorithm's Issues

1639. Number of Ways to Form a Target String Given a Dictionary

1. Meaning of dp[i][j]

$$ dp[i][j]=\text{num way to form target[0, j] using all word items[0, i] in words} $$

2. Reoccurrence Formula

$$ dp[i][j] = dp[i-1][j-1] * cnt[(i, target[j])+dp[i-1][j] $$

3. Dependencies Analysis

dp[i-1][j-1]	dp[i-1][j]
dp[i][j-1]	dp[i][j]

Traversal should be left to right and top to down, so to compute the subproblem first.

4. Base Cases
The first row and the first column should be pre-computed.

• For any i=0 and j > i will be all zero because no such word[0, i] can form target[0, j] due to the insufficient length.
• For any i >= j and j = 0, we can pre-computed numbers of way to form target[0] for 0 <= i < I word[i].

Recursive
Time: NM + TM

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        mod = 10**9 + 7
        m = len(words[0])
        cnt = [[0]*26 for _ in range(m)]
        for word in words:
            for i, c in enumerate(word):
                cnt[i][ord(c) - ord('a')] += 1
        # di for char index of a word
        # j for target
        @cache
        def dfs(di, j):
            if j == len(target):
                return 1
            if di == m:
                return 0 
            res = dfs(di+1, j)                        # not pick current di
            charidx = ord(target[j]) - ord('a')
            res += cnt[di][charidx] * dfs(di+1, j+1)  # pick the current di
            return res % mod
        return dfs(0,0)

DP

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        I = len(words[0])
        J = len(target)
        mod = 10**9 + 7 
        cnt = [[0]*26 for _ in range(I)]
        for word in words:
            for i, c in enumerate(word):
                cnt[i][ord(c) - ord('a')] += 1
        dp = [ [0]*J for _ in range(I) ]
        # dp[i][j] indicates num way to form target[..j] using word item[..i]
        # base case
        dp[0][0] = cnt[0][ord(target[0]) - ord('a')]
        for i in range(1, I):
            dp[i][0] += dp[i-1][0] + cnt[i][ord(target[0]) - ord('a')]

        for i in range(1, I):
            for j in range(1, J):
                cidx = ord(target[j]) - ord('a')
                dp[i][j] = ((dp[i-1][j-1]*cnt[i][cidx])%mod + dp[i-1][j])%mod
        return dp[-1][-1]

2218. Maximum Value of K Coins From Piles

Recursive Solution

class Solution:
    def maxValueOfCoins(self, A: List[List[int]], K: int) -> int:
        @cache
        def dp(i, k):
            if k == 0 or i == len(A): return 0
            res, cur = dp(i + 1, k), 0           # Not to pick coin at this pile
            for j in range(min(len(A[i]), k)):   # Pick coin at this pile
                cur += A[i][j]
                res = max(res, cur + dp(i+1, k-j-1))
            return res
        return dp(0, K)

DP

class Solution:
    """
    dp[i][j]: max value we pick at first i piles and with j coins
    suppose we pick x coins at i piles
    then to calculate the max value
    dp[i][j] = max{dp[i-1][j-x] + presum[i][x] for x = 0,1,2,3 ... maxpick}
    """
    def maxValueOfCoins(self, A: List[List[int]], k: int) -> int:
        n = len(A)
        dp = [ [0]*(k+1) for _ in range(n) ]
        presum = [0] * n 
        for i in range(n):
            cursum = 0
            presum[i] = [cursum]
            for j in range(len(A[i])):
                cursum += A[i][j]
                presum[i].append(cursum)
 
 
        for i in range(n):
            for j in range(k+1):
                # suppose at current pile we pick x coins
                maxpick = min(j, len(A[i])) + 1
                for x in range(maxpick):
                    if i == 0:
                        dp[i][j] = presum[i][x]
                    else:
                        dp[i][j] = max(dp[i][j], dp[i-1][j-x] + presum[i][x])
        return dp[n-1][k]

319. Bulb Switcher

Only the odd number toggle to a light that light will remain on since the initial state of light is off

we toggle lights for n rounds
each i round, ii, 2ii, 3i*i ... light will be toggled.