LeetCode算法题整理（动态规划篇）Danymic Programming

Posted on   |   Updated on | In | | Visitors

70. Climbing Stairs

爬楼梯，一次可以爬一阶或两阶楼梯，爬上n阶楼梯有多少种方法？原题

斐波那契问题

1
2
3
4
5
def fibonacci(n):
    a = b = 1
    for _ in range(n-1):
        a, b = b, a+b
    return b

746. Min Cost Climbing Stairs

楼梯上每层写了到达该层的卡路里，求上到顶层消耗的最小卡路里。原题

1
2
3
4
5
6
7
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

方法一：the final cost f[i] to climb the staircase from some step iis f[i] = cost[i] + min(f[i+1], f[i+2])。到达一层有两种选择，一种是上一层，一种是上两层。

1
2
3
4
5
def minCostClimbingStairs(self, cost: List[int]) -> int:
    f1 = f2 = 0
    for x in reversed(cost):
        f1, f2 = min(f1, f2) + x, f1
    return min(f1, f2)

121. Best Time to Buy and Sell Stock

买入卖出最大收益。原题

1
2
3
4
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

方法一：Brute Force.其实就是求最高峰点和前面最低谷点的差。

1
2
3
4
5
6
7
8
def maxProfit(self, prices: List[int]) -> int:
    ans, min_buy = 0, float('inf')
    for price in prices:
        if price < min_buy:
            min_buy = price
        elif price-min_buy > ans:
            ans = price - min_buy
    return ans
方法二：标准的卡登算法。此题为53.连续数组最大和的变形，如果价格比之前小，则舍弃，否则一起计算连续子数组的和。 
1
2
3
4
5
6
7
def maxProfit(self, prices: List[int]) -> int:
    cur = sofar = 0
    for i in range(1, len(prices)):
        cur += prices[i] - prices[i-1]
        cur = max(0, cur)
        sofar = max(cur, sofar)
    return sofar

122. Best Time to Buy and Sell Stock II

买入卖出，允许多次交易。原题

1
2
3
4
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

思路：比较每两天的价格，如果是涨价了，那就把收益计算进去，否则不出手交易。

1
2
3
4
5
6
def max_profit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit

方法二：pairwise.

1
2
3
4
5
6
7
8
def maxProfit(self, prices: List[int]) -> int:
    t, y = itertools.tee(prices)
    next(t, None)
    profit = 0
    for p1, p2 in zip(t, y):
        if p1 > p2:
            profit += p1-p2
    return profit

714. Best Time to Buy and Sell Stock with Transaction Fee

和122比较像，区别在于每次交易时有一定的手续费。

1
2
3
4
5
6
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1Selling at prices[3] = 8
Buying at prices[4] = 4Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

方法一：dp。和抢房子有点像。

1
2
3
4
5
def maxProfit(self, prices: List[int], fee: int) -> int:
    hold, unhold = -inf, 0
    for i, price in enumerate(prices):
        unhold, hold = max(unhold, hold+price-fee), max(hold, unhold-price)
    return unhold
方法二：想到了贪心方法，但没写出具体代码，思路是这样的，把交易费和买入价算到一起。买了之后肯定回去卖。 
1
2
3
4
5
6
7
8
9
10
def maxProfit(self, prices: List[int], fee: int) -> int:
    profit = 0
    buy = prices[0] + fee
    for i in range(1, len(prices)):
        if prices[i] + fee < buy:
            buy = prices[i] + fee
        elif prices[i] > buy:
            profit += prices[i] - buy
            buy = prices[i]  # 这里不能+buy，因为连续升高的股价，只需要卖一次即可
    return profit

Best Time to Buy and Sell Stock III

最多允许交易两次。原题

先从左到右按照一次交易计算每天的利润。然后按照从右到左，判断如果进行第二次交易，最大的利润。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def maxProfit(self, prices: List[int]) -> int:
    min_buy = float('inf')
    profits = []
    max_profit = 0
    for p in prices:
        min_buy = min(min_buy, p)
        max_profit = max(max_profit, p-min_buy)
        profits.append(max_profit)
    
    max_profit = 0
    total_profit = 0
    max_sell = float('-inf')
    for i in range(len(prices)-1, -1, -1):
        max_sell = max(max_sell, prices[i])
        max_profit = max(max_profit, max_sell-prices[i])
        total_profit = max(total_profit, max_profit+profits[i])
    return total_profit

188. Best Time to Buy and Sell Stock IV

最多允许交易K次。

方法一：三维dp数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxProfit(self, k: int, prices: List[int]) -> int:
    N = len(prices)
    # dp[i][j][0]表示prices[:i]进行j次交易后最后是卖出的最大利润
    # dp[i][j][1]表示prices[:i]进行j次交易后最后是买入的最大利润
    if k >= N//2:
        return sum(b-a for a, b in zip(prices, prices[1:]) if b>a)
    dp = [[[0, 0] for _ in range(k+1)] for _ in range(N)]
    for j in range(1, k+1):
        dp[0][j][0] = 0
        dp[0][j][1] = -prices[0]  # 以第一天的股票价格买入方便后续处理数据
    for i, p in enumerate(prices[1:], 1):
        for j in range(1, k+1):
            # 假设买入时增加一次交易
            dp[i][j][0] = max(dp[i-1][j][1]+p, dp[i-1][j][0])
            dp[i][j][1] = max(dp[i-1][j-1][0]-p, dp[i-1][j][1])
    return dp[-1][-1][0]

309. Best Time to Buy and Sell Stock with Cooldown

每次买卖股票后有一天的冷却期什么也不能干。原题

方法一：3个状态，5中状态转换。 

1
2
3
4
5
6
7
8
9
10
def maxProfit(self, prices: List[int]) -> int:
    # hold -> do_nothing -> hold
    # hold -> sell -> not_hold_cd
    # not_hold -> do_nothing -> not_hold
    # not_hold -> buy -> hold
    # not_hold_cd -> do_nothing -> not_hold
    not_hold, hold, not_hold_cd = 0, float('-inf'), float('-inf')
    for price in prices:
        hold, not_hold, not_hold_cd = max(hold, not_hold-price), max(not_hold, not_hold_cd), hold+price
    return max(not_hold, not_hold_cd)

LCP 19. 秋叶收藏集

杯赛里的题，说将字符串替换成r*y*r*的形式，最少需要多少步。原题

方法一：和309非常相似，记录3种状态。

1
2
3
4
5
6
7
8
9
def minimumOperations(self, leaves: str) -> int:
    # r 代表当前位置是 r* 型的替换次数
    # ry 代表当前位置是 r*y* 型的替换次数
    # ryr 分别代表当前位置是 r*y*r* 型的替换次数
    r, ry, ryr = int(leaves[0] == 'y'), float('inf'), float('inf')
    for i in range(1, len(leaves)):
        x = int(leaves[i] == 'y')
        r, ry, ryr = r+x, min(r, ry)+(1-x), min(ry, ryr)+x
    return ryr

198. House Robber

抢劫房子问题。不能连续抢劫两个挨着的房间。原题

1
2
3
4
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.
1
2
3
f(0) = nums[0]
f(1) = max(num[0], num[1])
f(k) = max( f(k-2) + nums[k], f(k-1) )

方法一：递归，超时。

1
2
3
4
5
6
7
def rob(self, nums):
    if not nums:
        return 0
    if len(nums) <= 1:
        return nums[0]
    return max(nums[0]+self.rob(nums[2:]), 
               self.rob(nums[1:]))

方法二：

1
2
3
4
5
def rob(self, nums):
    last, now = 0, 0
    for num in nums:
        last, now = now, max(last+num, now)
    return now

213. House Robber II

与上题不同的是，所有的房子连成一个环。原题

1
2
3
4
nput: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

方法一：注意nums长度为1的情况。

1
2
3
4
5
6
7
8
def rob(self, nums: List[int]) -> int:
    
    def robber(nums):
        last = now = 0
        for num in nums:
            last, now = now, max(last+num, now)
        return now
    return max(robber(nums[:-1]), robber(nums[len(nums)!=1:]))

303. Range Sum Query - Immutable

给定一个数组，计算索引i, j之间的和。原题

1
2
3
4
5
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

思路：如果单纯采用切片计算，效率过低，题中要求sumRange调用多次。所以这里采用动态规划。

1
2
3
4
5
6
7
8
9
10
11
12
13
class NumArray:
    
    def __init__(self, nums):
        # self.sum_item = [0]
        # for num in nums:
        #     self.sum_item.append(self.sum_item[-1] + num)
        from itertools import accumulate
        from operator import add
        self.sum_item = list(accumulate(nums, add))

    def sumRange(self, i, j):
        # return self.sum_item[j+1] - self.sum_item[i] 
        return self.sum_item[j] - self.sum_item[i-1] if i > 0 else self.sum_item[j]

91. Decode Ways

将数字翻译成字母有多少种方式。原题

1
2
3
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
1
2
3
4
5
6
7
8
9
def numDecodings(self, s: str) -> int:
    # w tells the number of ways
    # v tells the previous number of ways
    # d is the current digit
    # p is the previous digit
    v, w, p = 0, int(s>''), ''
    for d in s:
        v, w, p = w, int(d>'0')*w + (9<int(p+d)<27)*v, d
    return w

62. Unique Paths

一个矩阵中，从左上走到右下有多少种不同走法，每次只能向右或向下移动。原题

方法一：构建二维矩阵。

1
2
3
4
5
6
7
8
9
10
def uniquePaths(self, m: int, n: int) -> int:
    g = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i==0 or j==0:
                g[i][j] = 1
            else:
                g[i][j] = g[i-1][j] + g[i][j-1]
        
    return g[-1][-1]
方法二：二维数组时没有必要的，仔细观察发现每层都是累计的关系，accumulate为此而生。 
1
2
3
[1,  1,  1,   1,   1,   1,   1]
[1,  2,  3,   4,   5,   6,   7]
[1,  3,  6,  10,  15,  21,  28]
1
2
3
4
5
def uniquePaths(self, m: int, n: int) -> int:
    row = [1] * m
    for _ in range(n-1):
        row = itertools.accumulate(row)
    return list(row)[-1]

63. Unique Paths II

和62一样，不同的是中间加了障碍1。原题

1
2
3
4
5
6
7
Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2

方法一：首次AC的方法，这里采用先遍历一次记录障碍，然后初始化首行和首列，最后再求解的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def uniquePathsWithObstacles(self, g: List[List[int]]) -> int:
    R, C = len(g), len(g[0])
    
    for i in range(R):
        for j in range(C):
            if g[i][j] == 1:
                g[i][j] = -1
            
    for i in range(R):
        if g[i][0] != -1:
            g[i][0] = 1
        else:
            break
            
    for j in range(C):
        if g[0][j] != -1:
            g[0][j] = 1
        else:
            break
    for i in range(1, R):
        for j in range(1, C):
            if g[i][j] == -1:
                continue
            else:
                up = g[i-1][j] if g[i-1][j]!=-1 else 0
                left = g[i][j-1] if g[i][j-1]!=-1 else 0
                g[i][j] = up + left
                
    # print(g)
    return g[-1][-1] if g[-1][-1] != -1 else 0

方法二：想错了一件事情，我根本不需要去单独的设置障碍值，在遍历的时候就可以根据0来判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def uniquePathsWithObstacles(self, g: List[List[int]]) -> int:
    R, C = len(g), len(g[0])
    if g[0][0] == 1:
        return 0
    g[0][0] = 1
    for i in range(1, C):
        g[0][i] = int(g[0][i-1]==1 and g[0][i]==0)

    for j in range(1, R):
        g[j][0] = int(g[j-1][0]==1 and g[j][0]==0)

    for i in range(1, R):
        for j in range(1, C):
            if g[i][j] == 0:
                g[i][j] = g[i-1][j] + g[i][j-1]
            else:
                g[i][j] = 0
    return g[-1][-1]

120. Triangle

三角形从上到下最小路径。原题

1
2
3
4
5
6
7
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
i.e., 2 + 3 + 5 + 1 = 11

方法一：我这里使用了一个嵌套的字典保存每一行的累计最小值。

1
2
3
4
5
6
7
8
9
10
def minimumTotal(self, t: List[List[int]]) -> int:
    if not t:
        return 0
    from collections import defaultdict
    dp = defaultdict(lambda: defaultdict(lambda: float('inf')))
    dp[0][0] = t[0][0]
    for i, row in enumerate(t[1:], 1):
        for j, num in enumerate(row):
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + t[i][j]
    return min(dp[len(t)-1].values())
方法二：在原数组上修改，空间复杂度O(1). 
1
2
3
4
5
def minimumTotal(self, t: List[List[int]]) -> int:
    for i in range(len(t)-2, -1, -1):
        for j in range(i+1):
            t[i][j] += min(t[i+1][j], t[i+1][j+1])
    return t[0][0]
方法三：错位相加大法。空间复杂度O(n) 
1
2
3
4
5
6
7
8
def minimumTotal(self, t: List[List[int]]) -> int:

    def combine_rows(lower_row, upper_row):
        return [upper + min(lower_left, lower_right)
                for upper, lower_left, lower_right in 
                zip(upper_row, lower_row, islice(lower_row, 1, None))]

    return reduce(combine_rows, reversed(t))[0]

方法四：我按照方法三实现了一个纯的生成器版本。iter是防止t中只有一行的情况。这里我不确定是否将空间复杂度降低到了O(1)。

1
2
3
4
5
6
7
8
9
10
def minimumTotal(self, t: List[List[int]]) -> int:

    def combine_rows(lower_row, upper_row):
        lower_row, lower_row_nxt = tee(lower_row)
        next(lower_row_nxt, None)
        return (upper + min(lower_left, lower_right)
                for upper, lower_left, lower_right in 
                zip(upper_row, lower_row, lower_row_nxt))

    return next(iter(reduce(combine_rows, reversed(t))))

931. Minimum Falling Path Sum

和120相似，不过形状变成了矩形。原题

1
2
3
4
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:

方法一：常规写法。

1
2
3
4
5
6
7
def minFallingPathSum(self, A: List[List[int]]) -> int:
    R, C = len(A), len(A[0])
    for i in range(R-2, -1, -1):
        for j in range(C):
            path = slice(max(0, j-1), min(C, j+2))
            A[i][j] += min(A[i+1][path])
    return min(A[0])

方法二：错位计算的方式，这个比120三角形的要复杂一点。需要填充无穷大来使生效。

1
2
3
4
5
6
7
8
def minFallingPathSum(self, A: List[List[int]]) -> int:
    from functools import reduce
    padding = [float('inf')]
    def combine_rows(lower_row, upper_row):
        return [upper + min(lower_left, lower_mid, lower_right)
                for upper, lower_left, lower_mid, lower_right in
                zip(upper_row, lower_row[1:]+padding, lower_row, padding+lower_row[:-1])]
    return min(reduce(combine_rows, A[::-1]))

1289. Minimum Falling Path Sum II

上题变形，每行找到非自己那列的元素。原题

方法一：用堆记录2个最小的值。

1
2
3
4
5
6
7
def minFallingPathSum(self, arr: List[List[int]]) -> int:
    m, n = len(arr), len(arr[0])
    for i in range(1, m):
        r = heapq.nsmallest(2, arr[i-1])
        for j in range(n):
            arr[i][j] += r[1] if arr[i-1][j]==r[0] else r[0]
    return min(arr[-1])

279. Perfect Squares

完美平方，找出n的最少的能被几个平方数相加。原题

1
2
3
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

f(n)表示n最少的个数。f(n)=min(f(n-1²), f(n-2²)...f(0)) + 1

1
2
3
4
5
6
7
8
class Solution:
    _dp = [0]
    def numSquares(self, n: int) -> int:
        dp = self._dp
        while len(dp) <= n:
            # dp.append(min(dp[len(dp)-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1)
            dp.append(min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1)
        return dp[n]

5. Longest Palindromic Substring

最长回文子字符串。原题

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

方法一：O(n²)的方法。非常低效的一个做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def longestPalindrome(self, s: str) -> str:
    
    def helper(i, j):
        while i >=0 and j < len(s) and s[i]==s[j]:
            i -= 1
            j += 1
        return s[i+1:j]  # 因为i, j是不相等的。
    # ans = ''
    # for i, c in enumerate(s):
    #     tmp = helper(i, i)
    #     if len(tmp) > len(ans):
    #         ans = tmp
    #     tmp = helper(i, i+1)
    #     if len(tmp) > len(ans):
    #         ans = tmp
    # return ans
    return s and max((a for i in range(len(s)) 
                      for a in (helper(i, i), helper(i, i+1))), key=len) or ''
方法二：这个方法很好。从前到后遍历字符，一种是奇数长度的回文串，是增加两个长度，另一种是偶数长度的回文串，是增加一个长度。每次从当前字符向前做切片，并根据当前的最大长度控制切片长度。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longestPalindrome(self, s: str) -> str:
    if not s:
        return ''
    maxLen = 1
    start = 0
    for i in range(len(s)):
        if i-maxLen>=1 and s[i-maxLen-1:i+1]==s[i-maxLen-1:i+1][::-1]:
            start = i - maxLen - 1
            maxLen += 2
            continue

        if i-maxLen>=0 and s[i-maxLen:i+1]==s[i-maxLen:i+1][::-1]:
            # print(s[i-maxLen:i+1], s[i-maxLen:i+1][::-1])
            start = i - maxLen
            maxLen += 1 
    return s[start:start+maxLen]
方法三：马拉车算法。Time: O(n).

算法详解。这里是把一些情况做了整合。整个代码非常优雅。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def longestPalindrome(self, s: str) -> str:
    # Transform S into T.
    # For example, S = "abba", T = "^#a#b#b#a#$".
    # ^ and $ signs are sentinels appended to each end to avoid bounds checking
    T = '#'.join('^{}$'.format(s))
    n = len(T)
    P = [0] * n
    C = R = 0
    for i in range (1, n-1):
        P[i] = (R > i) and min(R - i, P[2*C - i]) # equals to i' = C - (i-C)
        # Attempt to expand palindrome centered at i
        while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
            P[i] += 1

        # If palindrome centered at i expand past R,
        # adjust center based on expanded palindrome.
        if i + P[i] > R:
            C, R = i, i + P[i]

    # Find the maximum element in P.
    maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
    return s[(centerIndex  - maxLen)//2: (centerIndex  + maxLen)//2]

1024. Video Stitching

影片剪辑，给定n组影片段，求能够拼出0~T完整影片所使用的最小段数。原题

1
2
3
4
5
6
7
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation: 
We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

方法一：此题竞赛时没有完成，想了字典的方法，老是纠结于怎么消除题中的[1, 5]段，其实根本没必要，迭代的时候维护两个变量，一个是已经能组成的最大时长，另一个是当前可以延长到的最大时长。看了Lee神的答案。有个地方比较难理解，假设输入是[[0,2], [1,9],[4,6]], T=9。按照逻辑如果全执行完，cnt应该=3。但是一旦end2覆盖了答案就及时break掉了，所以不会再累加。如果T10，那么即使cnt为3也会返回-1。

1
2
3
4
5
6
7
8
9
10
def videoStitching(self, clips: List[List[int]], T: int) -> int:
    end, end2, cnt = -1, 0, 0   # end 表示上一段最后截止点，end2表示当前可以最大延伸的最远地点。
    for s, e in sorted(clips):
        if end2 >= T or s > end2:   # 完成或者接不上了
            break
        elif end < s <= end2:       # 续1s
            cnt += 1
            end = end2
        end2 = max(end2, e)
    return cnt if end2 >= T else -1

1048. Longest String Chain

每个字符添加任意一个字符，可以组成一个字符串链。原题

1
2
3
4
5
6
7
8
9
10
11
12
13
def longestStrChain(self, words: List[str]) -> int:
    words2 = {i:set() for i in range(1, 17)}
    for word in words:
        words2[len(word)].add(word)
    dp = collections.defaultdict(lambda : 1)
    for k in range(2, 17):
        for w in words2[k]:
            for i in range(k):
                prev = w[:i] + w[i+1:]
                if prev in words2[k-1]:
                    # dp[w] = max(dp[w], dp[prev]+1)
                    dp[w] = dp[prev] + 1
    return max(dp.values() or [1])

1143. Longest Common Subsequence

最长公共子串的长度。原题

1
2
3
Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
import functools
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @functools.lru_cache(None)
        def helper(i,j):
            if i<0 or j<0:
                return 0
            if text1[i]==text2[j]:
                return helper(i-1,j-1)+1
            return max(helper(i-1,j),helper(i,j-1))
        return helper(len(text1)-1,len(text2)-1)

方法二：迭代。dp(i,j) means the longest common subsequence of text1[:i] and text2[:j].

1
2
3
4
5
6
7
8
9
10
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    n1, n2 = len(text1), len(text2)
    dp = [[0]*(n2+1) for i in range(n1+1)]
    for i in range(n1):
        for j in range(n2):
            if text1[i] == text2[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    return dp[-1][-1]

583. Delete Operation for Two Strings

最少删除多少次可以让两个字符串相等。原题

1
2
3
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

方法一：dp。这题一上来就发现和1143. Longest Common Subsequence一样。

1
2
3
4
5
6
7
def minDistance(self, word1: str, word2: str) -> int:
    n1, n2 = len(word1), len(word2)
    dp = [[0]*(n2+1) for _ in range(n1+1)]
    for i in range(n1):
        for j in range(n2):
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j]+(word1[i]==word2[j]))
    return n1+n2-dp[-1][-1]*2

712. Minimum ASCII Delete Sum for Two Strings

删除最小的ascii码的字符，使剩下的两个字符串相等。

方法一：同583.

1
2
3
4
5
6
7
8
9
10
def minimumDeleteSum(self, s1: str, s2: str) -> int:
    n1, n2 = len(s1), len(s2)
    dp = [[0] * (n2+1) for _ in range(n1+1)]
    for i in range(n1):
        for j in range(n2):
            if s1[i]==s2[j]:
                dp[i+1][j+1] = dp[i][j] + ord(s1[i])
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    return sum(map(ord, s1+s2)) - dp[-1][-1]*2

1312. Minimum Insertion Steps to Make a String Palindrome

将一个字符串变为回文串，最小插入字母步数。原题

1
2
3
4
5
6
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.
Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

方法一：和1134，Longest Common Subsequence一样，当这个字符串和他倒序的公共子串越多，需要添加的字母就越少。

1
2
3
4
5
6
7
def minInsertions(self, s: str) -> int:
    n = len(s)
    dp = [[0] * (n+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(n):
            dp[i+1][j+1] = dp[i][j] + 1 if s[i] == s[~j] else max(dp[i+1][j], dp[i][j+1])
    return n - dp[n][n]

221. Maximal Square

最大的正方形岛屿面积。原题

1
2
3
4
5
6
7
8
Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4
方法一：此题看似和最大岛屿面积相似，但解法完全不同。 
1
2
3
4
5
6
7
8
9
10
11
def maximalSquare(self, g: List[List[str]]) -> int:
    if not g: return 0
    M, N = len(g), len(g[0])
    dp = [[0] * (N+1) for _ in range(M+1)]
    max_side = 0
    for i in range(1, M+1):
        for j in range(1, N+1):
            if g[i-1][j-1] == '1':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                max_side = max(max_side, dp[i][j])
    return max_side ** 2
方法二：采用位运算。从评论区学到的写法，非常屌。假设从有h行数组，将这些数组表示的二进制数按位与，最大的连续的1的长度就是能组成最大正方形的宽度。由于查1的运算变成了位运算，所以时间复杂度和上述方法是一样的。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def maximalSquare(self, g: List[List[str]]) -> int:

    def count_serial_one(d):
        count = 0
        while d:
            d = d & (d<<1)
            count += 1
        return count

    if not g: return 0
    nums = [int(''.join(row), 2) for row in g]
    M = len(g)
    size = 0
    for i in range(M):
        cur_num = nums[i]
        for j in range(i, M):
            cur_num = cur_num & nums[j]
            w = count_serial_one(cur_num)
            if w < j-i+1: break  # 优化。因为w会越来越小，高会越来越大。
            size = max(size, min(w, j-i+1))
    return size ** 2

1340. Jump Game V

跳跃游戏，可以向左右d范围内矮的地方跳下。原题

1
2
3
4
5
Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.
1
2
3
4
5
6
7
8
9
10
11
12
def maxJumps(self, arr: List[int], d: int) -> int:
    n = len(arr)
    ans = [0] * n

    def jump(i):
        if ans[i]: return ans[i]
        ans[i] = 1
        for di in (-1, 1):
            for j in range(i+di, i+d*di+di, di):
                if not (0<=j<n and arr[j]<arr[i]): break
                ans[i] = max(ans[i], jump(j)+1)
        return ans[i]

1301. Number of Paths with Max Score

左上到右下，最大值，路径中存在障碍，并且需要返回路径的个数。原题

1
2
Input: board = ["E23","2X2","12S"]
Output: [7,1]

方法一：初次AC的方法。此题与剑指offer中礼物的最大值有点像，多了一个障碍，多了一种走法，多返回一个数量。这种解法对于带有障碍的问题来说 不太适合。但是速度上比方法二快了一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
    R, C = len(board), len(board[0])
    board[0] = '0' + board[0][1:]
    board[-1] = board[-1][:-1] + '0'
    b = [[float('-inf') if d=='X' else int(d) for d in row] for row in board]
    ways = [[0] * C for _ in range(R)]
    first_row = list(itertools.takewhile(lambda x: x>=0, ways[0]))
    ways[0] = len(first_row) * [1] + (C-len(first_row)) * [0]
    cur = list(itertools.accumulate(b[0]))
    for i in range(1, R):
        tmp = []
        for j in range(C):
            left = tmp[-1] if j>0 else float('-inf')
            dia = cur[j-1] if j>0 else float('-inf')
            max_pre = max(cur[j], dia, left)
            tmp.append(max_pre + b[i][j])
            left_way = ways[i][j-1] if j>0 else 0
            up_way = ways[i-1][j]
            dia_way = ways[i-1][j-1] if i>0 and j>0 else 0
            if max_pre != float('-inf') and b[i][j]!=float('-inf'):
                ways[i][j] += up_way * (cur[j]==max_pre)
                ways[i][j] += left_way * (left==max_pre)
                ways[i][j] += dia_way * (dia==max_pre)
        cur = tmp
    return (cur[-1] if cur[-1]!=float('-inf') else 0, 
            ways[-1][-1] % (10**9+7))
方法二：优化。构造一个+1的dp。lee215的解法。3个方向的延伸放到了循环中，同时记录最大的路径个数。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
    n, mod = len(board), 10**9+7
    dp = [[[float('-inf'), 0] for j in range(n+1)] for i in range(n+1)]
    dp[n-1][n-1] = [0, 1]
    for x in range(n)[::-1]:
        for y in range(n)[::-1]:
            if board[x][y] in 'XS': continue
            for i, j in ((0, 1), (1, 0), (1, 1)):
                if dp[x][y][0] < dp[x+i][y+j][0]:
                    dp[x][y] = [dp[x+i][y+j][0], 0]
                if dp[x][y][0] == dp[x+i][y+j][0]:
                    dp[x][y][1] += dp[x+i][y+j][1]
            dp[x][y][0] += int(board[x][y]) if x or y else 0
    return [dp[0][0][0] if dp[0][0][1] else 0, dp[0][0][1] % mod]

1277. Count Square Submatrices with All Ones

矩阵中最多有多少个1构成的正方形。原题

1
2
3
4
5
6
7
8
9
10
11
12
Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
1
2
3
4
5
6
7
8
9
def countSquares(self, mat: List[List[int]]) -> int:
    m, n = len(mat), len(mat[0])
    # dp[i][j] 表示以i, j为右下点时，正方形的个数。
    dp = [[0] * (n) for i in range(m)]
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 1:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    return sum(map(sum, dp))

1269. Number of Ways to Stay in the Same Place After Some Steps

回到原点的走法一共有多少种，一次只能向右，向左或者停留，要求始终保持在数组范围。原题

1
2
3
4
5
6
7
Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

方法一：找到状态转移方程，dp[p][s] = dp[p-1][s-1] + dp[p][s-1] + dp[p+1, s-1]p代表位置，s代表步数。首部添加0方便求和。注意t+3这个范围。

1
2
3
4
5
6
def numWays(self, steps: int, n: int) -> int:
    mod = 10**9 + 7
    A = [0, 1]
    for t in range(steps):
        A[1:] = [sum(A[i - 1:i + 2]) % mod for i in range(1, min(n + 1, t + 3))]
    return A[1] % mod

338. Counting Bits

返回从0到num的数中，每个数二进制中含有1的个数。原题

1
2
Input: 5
Output: [0,1,1,2,1,2]

方法一：此解法用了191的暴力解法。

1
2
3
4
5
6
7
8
9
def countBits(self, num: int) -> List[int]:
    ans = []
    def count(a):
        c = 0
        while a != 0:
            a &= a-1
            c += 1
        return c
    return map(count, range(0, num+1))
方法二：dp 。dp[i]=dp[i//2]+i&1 
1
2
3
4
5
def countBits(self, num: int) -> List[int]:
    dp = [0]
    for i in range(1, num+1):
        dp.append(dp[i>>1] + (i&1))
    return dp

1262. Greatest Sum Divisible by Three

最多的元素和能被3整除。原题

1
2
3
Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

方法一：数学方法，累加所有的数，和可能有三种情况：

  • 余 0 ，刚好整除。
  • 余1， 需要减去一个余1的数，或者两个余2的数。
  • 余2，减去一个余2的数，或者两个余1的数。

需要注意数字是否够用。

1
2
3
4
5
6
7
8
9
10
def maxSumDivThree(self, nums: List[int]) -> int:
    total = sum(nums)
    mod_1 = [n for n in nums if n%3==1]
    mod_2 = [n for n in nums if n%3==2]
    if total % 3 == 1:
        return total - min(min(mod_1), sum(heapq.nsmallest(2, mod_2) if len(mod_2)>=2 else [float('inf')]))
    elif total % 3 == 2:
        return total - min(min(mod_2), sum(heapq.nsmallest(2, mod_1) if len(mod_1)>=2 else [float('inf')]))
    else:
        return total
方法二：dp. 
1
2
3
4
5
6
7
8
9
10
11
12
13
def maxSumDivThree(self, nums: List[int]) -> int:
    # dp[pos][mod]
    # # 0  1  2
    # 0 3  0  0
    # 1 9  0  0 
    # 2 9  0  14
    # 3 15 10 14
    # 4 18 22 23
    dp = [0] * 3
    for a in nums:
        for j in dp[:]:
            dp[(j+a) % 3] = max(dp[(j+a) % 3], j+a)
    return dp[0]

72. Edit Distance

两个单词，将a变成b的最小步数，可以添加、删除，替换一个字母。原题

1
2
3
4
5
6
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

方法一：真是后悔没早点做这个题，这题解法下有一个方法将dp的问题从记忆化搜索的递归到实现的过程讲解的非常详细。这里从这样的一个递归开始演变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minDistance(self, word1, word2):
        """Naive recursive solution"""
        if not word1 and not word2:
            return 0
        if not word1:
            return len(word2)
        if not word2:
            return len(word1)
        if word1[0] == word2[0]:
            return self.minDistance(word1[1:], word2[1:])
        insert = 1 + self.minDistance(word1, word2[1:])
        delete = 1 + self.minDistance(word1[1:], word2)
        replace = 1 + self.minDistance(word1[1:], word2[1:])
        return min(insert, replace, delete)

到最终的形态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def minDistance(self, word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j
        
    for i in range(m):
        for j in range(n):
            if word1[i] == word2[j]:
                dp[i+1][j+1] = dp[i][j]
            else:
                dp[i+1][j+1] = min(dp[i+1][j], dp[i][j+1], dp[i][j]) + 1
    return dp[-1][-1]

322. Coin Change

找零问题，给你几种面值的硬币，不限制每种硬币的个数，问组成多少钱最少需要几个硬币。原题

1
2
3
Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

方法一：自己想的方法。

1
2
3
4
5
def coinChange(self, coins: List[int], amount: int) -> int:
    dp = [0] + [float('inf')] * amount
    for i in range(1, amount+1):
        dp[i] = min(dp[i-coin]+1 if i>=coin else float('inf') for coin in coins)
    return dp[-1] if dp[-1]!=float('inf') else -1

518. Coin Change 2

找钱问题，给你几种面值的硬币，不限制每种硬币的个数，问组成多少钱有多少种方法。原题

1
2
3
4
5
6
7
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

方法一：背包问题，看了答案。

dp[i - 1][j]: 完全不用当前硬币组成j有多少种组合
dp[i][j - coins[i - 1]] :使用至少一个当前硬币（与上面一条是互斥事件）组成组成j有多少组合。for循环不能写反了，比如1+5和5+1同样能组成6，被算了两次。

1
2
3
4
5
6
7
8
def change(self, amount: int, coins: List[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for i in coins:
        for j in range(1, amount + 1):
           if j >= i:
               dp[j] += dp[j - i]
    return dp[amount]

1220. Count Vowels Permutation

元音字母的全排列，根据指定规则的，求全排列的个数。原题

1
2
3
Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

方法一：没想到居然做出来了。dp分别代表了以这些字母开头的个数。

1
2
3
4
5
6
7
8
9
10
11
def countVowelPermutation(self, n: int) -> int:
    dp = [1] * 5
    for _ in range(n-1):
        tmp = [[0] for _ in range(5)]
        tmp[0] = dp[1]
        tmp[1] = dp[0] + dp[2]
        tmp[2] = dp[0] + dp[1] + dp[3] + dp[4]
        tmp[3] = dp[2] + dp[4]
        tmp[4] = dp[0]
        dp = tmp
    return sum(dp) % (10**9+7)
方法二：一整得有点复杂了。 
1
2
3
4
5
def countVowelPermutation(self, n: int) -> int:
    a = e = i = o = u = 1
    for _ in range(n-1):
        a, e, i, o, u = e, a+i, a+e+o+u, i+u, a
    return (a+e+i+o+u) % (10**9+7)

368. Largest Divisible Subset

最大的整除子集。原题

1
2
Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)

方法一：stefan的解法。自己没想出来。

1
2
3
4
5
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
    S = {-1: set()}
    for x in sorted(nums):
        S[x] = max((S[d] for d in S if x % d == 0), key=len) | {x}
    return list(max(S.values(), key=len))

5456. Kth Ancestor of a Tree Node

找出一个树节点的k个祖先。原题

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

Output:
[null,1,0,-1]

Explanation:
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1);  // returns 1 which is the parent of 3
treeAncestor.getKthAncestor(5, 2);  // returns 0 which is the grandparent of 5
treeAncestor.getKthAncestor(6, 3);  // returns -1 because there is no such ancestor

方法一：这道题没有做出来，Lee的答案。用的倍增法，binary lifting.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class TreeAncestor:

    step = 15
    def __init__(self, n, A):
        A = dict(enumerate(A))
        jump = [A]
        for s in range(self.step):
            B = {}
            for i in A:
                if A[i] in A:
                    B[i] = A[A[i]]
            jump.append(B)
            A = B
        self.jump = jump
        print(jump)

    def getKthAncestor(self, x: int, k: int) -> int:
        step = self.step
        while k > 0 and x > -1:
            if k >= 1 << step:
                x = self.jump[step].get(x, -1)
                k -= 1 << step
            else:
                step -= 1
        return x

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

找到数组中等于目标值的两个不重叠子数组的最小长度和。原题

1
2
3
Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

方法一：看了提示后使用了前后遍历法做出来的。其实有一次遍历的方式。这个方法看了挺长时间，才明白，实际上记录了一个以end为结尾的前面的所有元素最好的长度是多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def minSumOfLengths(self, arr: List[int], target: int) -> int:
    prefix = {0: -1}
    best_till = [math.inf] * len(arr)
    ans = best = math.inf
    for i, curr in enumerate(itertools.accumulate(arr)):
        # print(i, curr)
        if curr - target in prefix:
            end = prefix[curr - target]
            if end > -1:
                ans = min(ans, i - end + best_till[end])
            best = min(best, i - end)
            # print('\t', best, i-end, best_till, ans)
        best_till[i] = best
        prefix[curr] = i
    return -1 if ans == math.inf else ans

494. Target Sum

给你一组数，用+或-连接起来最后等于target，问有多少种填法。原题

1
2
3
4
5
6
7
8
9
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

方法一：记忆化搜索。

1
2
3
4
5
6
7
8
9
10
11
def findTargetSumWays(self, nums: List[int], S: int) -> int:
    n = len(nums)

    @lru_cache(None)
    def dfs(i, total):
        if i == n:
            return total==S
        ans = dfs(i+1, total+nums[i]) + dfs(i+1, total-nums[i])
        return ans

    return dfs(0, 0)

174. Dungeon Game

地牢游戏，从左上走到右下，每次只能像右或者向下，格子里会扣血和加血，问最少需要多少血，全程保持血量为1以上。原题

方法一：这道题曾经面试某公司的时候做过，只是那道题还要求返回路径，当时做的时候以为做对了。再次遇见此题时想了一晚上发现想简单了。一开始想保留两个变量，一个是最少血量，一个是累加和。然后根据最少血量判断选择走哪条路，结果一个case证明了想法是错的。还是评论区找的写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
    R, C = len(dungeon), len(dungeon[0])
    dp = [[0] * C for _ in range(R)] 
    for i in range(R-1, -1, -1):
        for j in range(C-1, -1, -1):
            if i == R-1 and j == C-1:
                dp[i][j] = max(1, 1 - dungeon[i][j])
            elif i == R-1:
                dp[i][j] = max(1, dp[i][j+1] - dungeon[i][j])
            elif j == C-1:
                dp[i][j] = max(1, dp[i+1][j] - dungeon[i][j])
            else:
                dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
    return dp[0][0]

96. Unique Binary Search Trees

不重复的二叉搜索树，1~n节点。原题

1
2
3
4
5
6
7
8
9
10
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

方法一：这题看了答案，状态转移方程式这样的G(n)表示n个节点能组成的二叉搜索树节点个数。F(i, n)表示有n个节点时，以i为root的个数。G(n) = F(1, n) + F(2, n) + ... + F(n, n). F(3, 7)=G(2)*G(4)即F(i, n) = G(i-1) * G(n-i), 所以最后G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)

1
2
3
4
5
6
7
def numTrees(self, n: int) -> int:
    G = [0] * (n+1)
    G[0] = G[1] = 1
    for i in range(2, n+1):
        for j in range(1, i+1):
            G[i] += G[j-1]*G[i-j]
    return G[n]

95. Unique Binary Search Trees II

这题和96一样，要求将所有的树找出来。原题

方法一：第一次AC的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def generateTrees(self, n: int) -> List[TreeNode]:

    memo = {}

    def build(lo, hi):
        if (lo, hi) in memo: return memo[(lo, hi)]
        ans = []
        if lo > hi:
            return [None]
        elif lo == hi:
            return [TreeNode(lo)]
        for i in range(lo, hi+1):
            root = TreeNode(i)
            for left in build(lo, i-1):
                root.left = left
                for right in build(i+1, hi):
                    root.right = right
                    ans.append(copy.deepcopy(root))
        memo[(lo, hi)] = ans
        return ans

    return build(1, n) if n>0 else []

方法二：看了stefan的答案，更正一下自己的方法，lo==hi是没必要的，之前因为先考虑这个因素，没有删掉。deepcopy可以写成别的形式，在内循环生成root节点，而不是在外层生成一个再去拷贝。记忆化搜索也是没有必要的。用时比原来快了3倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def generateTrees(self, n: int) -> List[TreeNode]:
    
    def build(lo, hi):
        ans = []
        for i in range(lo, hi+1):
            for left in build(lo, i-1):
                for right in build(i+1, hi):
                    root = TreeNode(i)
                    root.left = left
                    root.right = right
                    ans.append(root)
        return ans or [None]
        
    return build(1, n) if n>0 else []

337. House Robber III

抢劫房子，房子是二叉树结构，不能抢两个挨着的节点，问最多可以抢多少。原题

方法一：看了讨论区才解出来。对于一个节点来说，只有两种case：抢与不抢。将这个条件利用起来代入到递归判断中

1
2
3
4
5
6
7
8
9
10
11
def rob(self, root: TreeNode) -> int:

    def dfs(node):
        if not node:
            return 0, 0
        left, right = dfs(node.left), dfs(node.right)
        not_rob = max(left) + max(right)
        robbed = node.val + left[0] + right[0]
        return not_rob, robbed

    return max(dfs(root))

1504. Count Submatrices With All Ones

查找有多少个由1组成的子矩阵。原题

1
2
3
4
5
6
7
8
9
10
11
Input: mat = [[1,0,1],
              [1,1,0],
              [1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

方法一：竞赛时未做出来，有道类似的题是求正方形的，所以思路被限制了，找到一个状态转移方程，但是case1跑不过，未注意变量的范围，其实O(MMN)的时间复杂度也是允许的。从1D扩展的2D，然后h表示当前列k的top到down是否都是1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def numSubmat(self, mat: List[List[int]]) -> int:
    R, C = len(mat), len(mat[0])
    ans = 0
   
    def count_row(a):
        ans = l = 0
        for num in a:
            l = 0 if num==0 else l+1
            ans += l
        return ans
    
    for top in range(R):
        h = [1] * C
        for bottom in range(top, R):
            for k in range(C):
                h[k] &= mat[bottom][k]
            ans += count_row(h)
    
    return ans

1140. Stone Game II

和1不一样，这回的规则是这样的，每次拿前m <= x <= 2m个堆，问最后Alex可以拿多少最多。原题

1
2
3
Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

方法一：没做出来，Lee的答案看了半天，退出条件开始很难想出来。就是如果能够全拿，就退出。转移方程式这样的，A变成了一个从后累加的数组，当前的人拿i~i+x另外的人就是dp[i+x, max(m, x)]

1
2
3
4
5
6
7
8
9
10
11
def stoneGameII(self, A: List[int]) -> int:
    N = len(A)
    for i in range(N - 2, -1, -1):
        A[i] += A[i + 1]
        
    from functools import lru_cache
    @lru_cache(None)
    def dp(i, m):
        if i + 2 * m >= N: return A[i]
        return A[i] - min(dp(i + x, max(m, x)) for x in range(1, 2 * m + 1))
    return dp(0, 1)

1510. Stone Game IV

这次是有n堆石头，每次可以拿平方数堆，如果谁拿不了了，谁就输了。

1
2
3
4
5
Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). 
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).

方法一：递归+记忆化，这里注意要从大到小遍历，开始写反了超时了一次。这里发现j*j比j**2快130ms，不明原因。240ms。

1
2
3
4
5
def winnerSquareGame(self, n: int) -> bool:
		@lru_cache(None)
    def dp(i):
        return not all(dp(i-j*j) for j in range(int(sqrt(i)), 0, -1))
    return dp(n)

方法二：迭代。Lee的迭代用了1000ms，这次没我写得好。我稍微改了一下，使它降到了700ms，不过还是很慢。

1
2
3
4
5
def winnerSquareGame(self, n: int) -> bool:
    dp = [False] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = not all(dp[i - k * k] for k in range(int(sqrt(i)), 0, -1))
    return dp[-1]

1686. Stone Game VI

两人从任意位置拿石头，每个石头对于两个人的价值不一样。两人都按最优方式拿，最后1表示Alice赢，0表示平局。

1
2
3
4
5
6
Input: aliceValues = [2,4,3], bobValues = [1,6,7]
Output: -1
Explanation:
Regardless of how Alice plays, Bob will be able to have more points than Alice.
For example, if Alice takes stone 1, Bob can take stone 2, and Alice takes stone 0, Alice will have 6 points to Bob's 7.
Bob wins.

方法一：比赛时想出来了，里面有个贪心的思想，对于一个石头来说，每个人都优先拿对于两个人价值都高的，所以这里是以累加为条件作为排序。

1
2
3
4
5
def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
    values = sorted(zip(aliceValues, bobValues), key=lambda x: x[0]+x[1], reverse=True)
    a = sum(v[0] for v in values[::2])
    b = sum(v[-1] for v in values[1::2])
    return (0, 1, -1)[(a>b)-(a<b)]

1524. Number of Sub-arrays With Odd Sum

求一个数组的和为奇数的子数组的个数。原题

1
2
3
4
5
Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

方法一：这题作为竞赛2题没做上，导致周赛排名降了不少。odd表示前i个数包含i的子数组奇数的个数。even则是偶数个数。那么当i+1为偶数时，even+1，奇数不变；当i+1为奇数时，even=odd，even=odd+1

1
2
3
4
5
6
7
8
def numOfSubarrays(self, arr: List[int]) -> int:
    ans = odd = even = 0
    for x in arr:
        even += 1
        if x % 2:
            odd, even = even, odd
        ans = (ans + odd) % (10**9+7)
    return ans

139. Word Break

问s是否能拆成words里的单词，单词可以重复使用。原题

1
2
3
4
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

方法一：还是想不到dp的解法。此题需要逆向思维。

1
2
3
4
5
6
7
def wordBreak(self, s: str, words: List[str]) -> bool:
    dp = [True] + [False] * len(s)
    for i in range(1, len(s)+1):
        for w in words:
            if s[:i].endswith(w):
                dp[i] |= dp[i-len(w)]
    return dp[-1]

方法二：递归倒是想到了。

1
2
3
4
5
6
7
8
9
10
11
12
13
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    word_set = set(wordDict)
    
    @lru_cache(None)
    def dfs(w):
        if not w:
            return True
        for word in word_set:
            if w.startswith(word) and dfs(w[len(word):]):
                return True
        return False
    
    return dfs(s)

140. Word Break II

和上题一样，不过要求返回所有拆分的结果。原题

1
2
3
4
5
6
7
8
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

方法一：回溯法，这里有个case会超时，所以判断了一下s是否有单独的字符出现。这个方法不太好，LC的例子有点弱，我将用例修改为"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]超出内存限制了。好叭，方法二也没过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def wordBreak(self, s: str, words: List[str]) -> List[str]:
    
    words = set(words)
    if set(s)-set(c for w in words for c in w):
        return []
    def backtrack(s, p):
        if not s:
            ans.append(' '.join(p))
        for i in range(1, len(s)+1):
            if s[:i] in words:
                backtrack(s[i:], p+[s[:i]])
    
    ans = []
    backtrack(s, [])
    return ans
方法二：记忆化搜索。需要用索引作key来完成。不能用s是因为，s可能是前后有重复值。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def wordBreak(self, s: str, words: List[str]) -> List[str]:
    
    words = set(words)
    memo = {len(s): ['']}
    
    def sentences(i):
        if i not in memo:
            memo[i] = [s[i:j] + (tail and ' ' + tail)
                       for j in range(i+1, len(s)+1)
                       if s[i:j] in words
                       for tail in sentences(j)]
        return memo[i]
        
    return sentences(0)

1416. Restore The Array

字符串s是有1~k个数非0开头组成的，问有多少种组成的方式。原题

1
2
3
4
5
6
7
8
9
10
11
Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

方法一：首次ac的方法。第10行如果不取余，时间慢了一倍，空间多了好几倍。这个思路和Word Break有点像，dp[i]表示s[:i]总共的组成方式。

1
2
3
4
5
6
7
8
9
10
11
12
def numberOfArrays(self, s: str, k: int) -> int:
    mod = 10 ** 9 + 7
    
    dp = [0] * (len(s) + 1)
    dp[0] = 1
    for i in range(1, len(s)+1):
        j = i-1
        while j>=0 and len(s[j:i])<=len(str(k)) and int(s[j:i]) <= k:
            if s[j] != '0':
                dp[i] += dp[j] % mod
            j -= 1
    return dp[-1] % mod

方法二：针对方法一优化，while循环看着有点乱。

1
2
3
4
5
6
7
8
9
10
11
def numberOfArrays(self, s: str, k: int) -> int:
    mod = 10 ** 9 + 7
    
    k_len = len(str(k))
    dp = [0] * (len(s) + 1)
    dp[0] = 1
    for i in range(1, len(s)+1):
        for j in range(max(0, i-k_len), i):
            if s[j] != '0' and int(s[j:i]) <=k:
                dp[i] += dp[j] % mod
    return dp[-1] % mod
方法三：用dp[i]表示[i:]总共的组成数量，从后向前计算，这样有一个好处，可以用数值来判断而不是字符串。此方法在时间上比上述快了一倍。为此作了很多实验，时间的消耗正是在s的反复切片中。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def numberOfArrays(self, s: str, k: int) -> int:
    mod = 10 ** 9 + 7
    n = len(s)
    s = [*map(int, s)] + [math.inf]      
    dp = [0] * n + [1]
    
    for i in range(n-1, -1, -1):
        num = s[i]
        for j in range(i+1, n+1):
            if 1 <= num <= k:
                dp[i] = (dp[i] + dp[j]) % mod
                num = 10 * num + s[j]
            else:
                break
    
    return dp[0]

1537. Get the Maximum Score

两个不重复数字的数组，从某个数组从左向右找一条路径，使值最大，如果和另一个数组有重复的数字则可以跳到另一个数组上。原题

方法一：竞赛时没有时间想，不过做起来比第3题简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
    
    def get_cross(arr1, arr2):
        a = [0]
        p = False
        s2 = set(arr2)
        for n in arr1:
            if not p:
                a.append(a.pop()+n)
            else:
                a.append(n)
            p = n in s2
        return a

    a1, a2 = get_cross(nums1, nums2), get_cross(nums2, nums1)
        
    ans = 0
    for a, b in itertools.zip_longest(a1, a2, fillvalue=0):
        ans = (ans + max(a, b)) % (10**9+7)
    return ans
方法二：忽略了一个条件，两个数组时有序的，所以可以使用双指针，O(1)的空间来实现。by@lee215. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def maxSum(self, A: List[int], B: List[int]) -> int:
    i, j, n, m = 0, 0, len(A), len(B)
    a, b, mod = 0, 0, 10**9+7
    while i<n or j<m:
        if i<n and (j==m or A[i]<B[j]):
            a += A[i]
            i += 1
        elif j<m and (i==n or A[i]>B[j]):
            b += B[j]
            j += 1
        else:
            a = b = max(a, b) + A[i]
            i += 1
            j += 1
    return max(a, b) % mod

1553. Minimum Number of Days to Eat N Oranges

每天可以吃一个橙子；或者被2整除时吃一半；或者被3整除时吃3分之2。问最少几天可以吃完原题

1
2
3
4
5
6
7
8
Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.

方法一：比赛时未做出来，想初始化一个2*10**9的数组，结果内存溢出。而且取余也没想出来。

1
2
3
4
5
6
class Solution:
    @functools.lru_cache()
    def minDays(self, n: int) -> int:
        if n <= 1:
            return n
        return 1 + min(self.minDays(n//2)+n%2, self.minDays(n//3)+n%3)

方法二：bfs，这个方法完全没有想到，就是将3种吃法放到队列中去。这种时间效率比方法一低很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
def minDays(self, n: int) -> int:
    q = collections.deque([(n, 0)]) 
    seen = set()
    while q:
        cur, step = q.popleft()
        if cur == 0:
            return step
        seen.add(cur)
        if cur-1 not in seen: q.append((cur-1, step+1))
        if cur&1==0 and cur//2 not in seen:     
            q.append((cur//2, step+1))
        if cur%3==0 and cur//3 not in seen:
            q.append((cur//3, step+1))

801. Minimum Swaps To Make Sequences Increasing

最少多少次对应位置的交换可以使两个数组都严格地单调递增。原题

1
2
3
4
5
6
7
Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation: 
Swap A[3] and B[3].  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.

方法一：在提交错一次get新case后做了出来。首次AC的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def minSwap(self, A: List[int], B: List[int]) -> int:
    last_swap = last_not_swap = 0
    A = [float('-inf')] + A
    B = [float('-inf')] + B
    for i in range(1, len(A)):
        cur_swap = cur_not_swap = float('inf')
        if A[i] > A[i-1] and B[i] > B[i-1]:
            cur_swap = last_swap + 1
            cur_not_swap = last_not_swap
        if A[i] > B[i-1] and B[i] > A[i-1]:
            cur_swap = min(cur_swap, last_not_swap+1)
            cur_not_swap = min(cur_not_swap, last_swap)
        last_swap, last_not_swap = cur_swap, cur_not_swap
    return min(last_swap, last_not_swap)

方法二：看了lee的答案，改了一下初始化的值，补负无穷是没必要的

1
2
3
4
5
6
7
8
9
10
11
12
def minSwap(self, A: List[int], B: List[int]) -> int:
    last_swap, last_not_swap = 1, 0
    for i in range(1, len(A)):
        cur_swap = cur_not_swap = len(A)
        if A[i] > A[i-1] and B[i] > B[i-1]:
            cur_swap = last_swap + 1
            cur_not_swap = last_not_swap
        if A[i] > B[i-1] and B[i] > A[i-1]:
            cur_swap = min(cur_swap, last_not_swap+1)
            cur_not_swap = min(cur_not_swap, last_swap)
        last_swap, last_not_swap = cur_swap, cur_not_swap
    return min(last_swap, last_not_swap)

837. New 21 Game

新的21点游戏，有个W面的骰子，少于K的时候要一直掷骰子，直到和超过K，问最后结果小于等于N的概率。原题

1
2
3
4
5
6
7
Input: N = 6, K = 1, W = 10
Output: 0.60000
Explanation:  Alice gets a single card, then stops.
In 6 out of W = 10 possibilities, she is at or below N = 6 points.

Input: N = 21, K = 17, W = 10
Output: 0.73278
方法一：超时，这道题让我联想到剑指offer中的骰子题，但是不太一样，所以这个方法和那个有点类似，但是超时了。此题的时间要求很高。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def new21Game(self, N: int, K: int, W: int) -> float:
    if K == 0: return 1
    last_p = collections.defaultdict(int)
    last_p[0] = 1
    ans = 0
    for i in range(K):
        new_p = collections.defaultdict(int)
        for j in range(i+1, N+1):
            if j >= K:
                ans += sum(last_p[j-m] for m in range(1, W+1) if j-m<K) / W
            else:
                new_p[j] = sum(last_p[j-m] for m in range(1, W+1) if j-m<K) / W

        last_p = new_p
        # print(i, last_p)
    return ans
方法二：这是Lee的答案，这题也是Lee贡献的，想了半天才想明白。想通了原理就不难理解，方法一就是没转过来弯。p(K) = p(K-1) / W + p(K-2) / W + p(K-3) / W + ... p(K-W) / W ，然后Wsum其实就是p(K-1)+p(K-2)+...p(K-W)，想象成一个W长度的滑动窗口，然后i<K是因为如果i达到了K，就已经截止了，所以概率不再累加了。 
1
2
3
4
5
6
7
8
9
10
def new21Game(self, N: int, K: int, W: int) -> float:
    from fractions import Fraction
    if K == 0 or N >= K + W: return 1
    dp = [1.0] + [0.0] * N
    Wsum = 1.0
    for i in range(1, N + 1):
        dp[i] = Wsum / W
        if i < K: Wsum += dp[i]
        if i - W >= 0: Wsum -= dp[i - W]
    return sum(dp[K:])

808. Soup Servings

有两种汤，有四种上法，如果一种汤不够，那都全都上了。问A汤先卖完的概率加上一起卖完的概率的一半，和是多少。原题

1
2
3
4
5
Example:
Input: N = 50
Output: 0.625
Explanation: 
If we choose the first two operations, A will become empty first. For the third operation, A and B will become empty at the same time. For the fourth operation, B will become empty first. So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.
方法一：递归，爆栈了，因为N最大为10^9。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def soupServings(self, N: int) -> float:
    
    @functools.lru_cache()
    def get_p(a, b):
        if a <= 0:
            if b <= 0:
                return 0, 1
            else:
                return 1, 0
        if b <= 0:
            return 0, 0
        a_0 = two_0 = 0
        for i in range(0, 100, 25):
            p1, p2 = get_p(a-100+i, b-i)
            a_0 += p1 / 4
            two_0 += p2 / 4
        # print(a, b, a_0, ' - ', two_0)
        return a_0, two_0
    
    p1, p2 = get_p(N, N)
    return p1 + 0.5*p2
方法二：Lee的方法。同时为0的情况，可以直接将概率减半，因为后序不会再此概率上再做计算。但就这样的话还是无法解决爆栈的问题。然后寻找规律，A汤4种情况平均下来，消耗地比B多，那么N越大，B先卖完的概率就越小，结果就越大。答案在5位小数精度内都算正确，所以找到一个阈值，概率变为1。然后对于25ml这个条件，可以将其看作一勺单位，这样计算起来比较简单。 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    memo = {}
    def soupServings(self, N):
        if N > 4800: return 1
        def f(a, b):
            if (a, b) in self.memo: return self.memo[a, b]
            if a <= 0 and b <= 0: return 0.5
            if a <= 0: return 1
            if b <= 0: return 0
            self.memo[(a, b)] = 0.25 * (f(a - 4, b) + f(a - 3, b - 1) + f(a - 2, b - 2) + f(a - 1, b - 3))
            return self.memo[(a, b)]
        N = math.ceil(N / 25.0)
        return f(N, N)

983. Minimum Cost For Tickets

最小花费的票钱，有三种通票，分别能旅行1，7，30天，对应三种价格，要在一年中的旅行日花费最少，需要多少钱。原题

1
2
3
4
5
6
7
8
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.

方法一：想了一会儿就做出来了，需要注意如果不是旅行日，要等于前一天的花费。

1
2
3
4
5
6
7
8
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
    dp = [0] + [float('inf')] * days[-1]
    for i in range(1, days[-1]+1):
        if i not in set(days):
            dp[i] = dp[i-1]
            continue
        dp[i] = min((dp[i-d] if i-d>=0 else 0) + cost for d, cost in zip([1, 7, 30], costs))
    return dp[-1]

473. Matchsticks to Square

将长度列表的火柴棍拼成正方形。不能折断某个火柴，但可以连接。原题

1
2
3
4
5
6
7
8
9
Input: [1,1,2,2,2]
Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Input: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

方法一：dfs ，效率不是很高。sort很重要，如果优先拿的不是最大的，那么将会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def makesquare(self, nums: List[int]) -> bool:
    if len(nums)<4 or sum(nums) % 4: return False
    target = sum(nums) // 4
    if max(nums) > target: return False
    nums.sort()
    
    def dfs(edges):
        # if all(d==target for d in edges): return True
        if not nums: return True
        cur = nums.pop()
        
        for i in range(4):
            if edges[i] + cur <= target:
                edges[i] += cur
                if dfs(edges): return True
                edges[i] -= cur
        nums.append(cur)
        return False
    
    return dfs([0]*4)
方法二：bitmask+ dp。这个方法研究了很长时间，忽略了A[bit]>cur下的break，让我对输出疑惑了很久，mask是一个N长度的都是1的二进制数，每次从右到左数第[i]位设为0 表示A[i]已经使用了，cur表示当前边剩下的长度，如果为0，表示一个边已经准备好，重新再设为T。原答案用的A排序是正序，我改成了倒序，又快了一倍，但是感觉这个跟cases是密切相关的，这个方法非常快，最快仅用40ms。比方法一快得多。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def makesquare(self, A: List[int]) -> bool:
    if len(A) < 4 or sum(A) % 4 or max(A) > sum(A) / 4:
        return False

    T = sum(A) // 4
    N = len(A)
    A.sort(reverse=True)

    memo = {}
    def dp(mask, cur = T):
        # print(format(mask, 'b').rjust(N, '0'), cur)
        if (mask, cur) in memo:
            return memo[mask, cur]
        if mask == 0: return cur == 0
        if cur == 0: return dp(mask, T)

        ans = False
        for bit in range(N):
            if mask & (1 << bit):
                if A[bit] > cur:
                    break
                # print('\t', format(mask, 'b').rjust(N, '0'), cur, bit)
                if dp(mask ^ (1 << bit), cur - A[bit]):
                    ans = True
                    break
        memo[mask, cur] = ans
        return ans
    
    ans = dp(2**N - 1)
    return ans

799. Champagne Tower

这题蛮有意思，说一个香槟塔，从塔尖倒酒，倒指定杯数的酒，然后问第几行第几个杯子是有多少酒。原题

方法一：想象每行前后多两个空杯，方便计算。

1
2
3
4
5
6
7
8
9
def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
    row = [poured]
    for r in range(1, query_row+1):
        tmp_row = [0] + row + [0]
        a, b = itertools.tee(iter(tmp_row))
        next(b, None)
        row = [max((l-1)*0.5, 0) + max((r-1)*0.5, 0)
               for l, r in zip(a, b)]
    return min(row[query_glass], 1)

方法二：Lee的方法和我的差不多，但是空间上比较小。

1
2
3
4
5
6
def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
    res = [poured] + [0] * query_row
    for row in range(1, query_row + 1):
        for i in range(row, -1, -1):
            res[i] = max(res[i] - 1, 0) / 2.0 + max(res[i - 1] - 1, 0) / 2.0
    return min(res[query_glass], 1)

486. Predict the Winner

两个选手每次从一堆球的两边拿，每人都是最优解，问最后A是否能赢。原题

1
2
3
4
5
6
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return False.

方法一：主要找到公式。递归。dp[i][j]表示从i~j最大能赢多少分。

1
2
3
4
5
6
7
8
9
10
11
def PredictTheWinner(self, nums: List[int]) -> bool:
    memo = {}
    
    def pick(i, j):
        if (i, j) not in memo:
            if i == j:
                return nums[i]
            memo[(i, j)] = max(nums[i]-pick(i+1, j), nums[j]-pick(i, j-1))
        return memo[(i, j)]
    
    return pick(0, len(nums)-1) >= 0

方法二：迭代的方法更新顺序不太好想，s表示长度。

1
2
3
4
5
6
7
8
9
10
def PredictTheWinner(self, nums: List[int]) -> bool:
     dp = [[0] * len(nums) for _ in range(len(nums))]
     for s in range(len(nums)):
         for i in range(len(nums)-s):
             j = i + s
             if i == j:
                 dp[i][i] = nums[i]
             else:
                 dp[i][j] = max(nums[j] - dp[i][j-1], nums[i] - dp[i+1][j])
     return dp[0][-1] >= 0

576. Out of Boundary Paths

将球踢出边界的路径数量，步数在N步之内。原题

方法一：比较直观的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:
    mod = 10**9 + 7
    g = [[0] * n for _ in range(m)]
    g[i][j] = 1
    
    def count():
        total = 0
        total += sum(g[0][j] for j in range(n))
        total += sum(g[m-1][j] for j in range(n))
        total += sum(g[i][0] for i in range(m))
        total += sum(g[i][n-1] for i in range(m))
        return total
    
    ans = 0
    for k in range(N):
        ans = (ans + count()) % mod
        new_g = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                new_g[i][j] += g[i-1][j] if i else 0
                new_g[i][j] += g[i+1][j] if i<m-1 else 0
                new_g[i][j] += g[i][j-1] if j else 0
                new_g[i][j] += g[i][j+1] if j<n-1 else 0
        g = new_g
    return ans
方法二：从边界到目标点。这个要这样想比如例子2，一步的时候是[3,2,3]，第二步是[5,8,5]，第3步是[11,12,11]，当从2加到3步时，两边的点1~2步的结果，加了一步，可以从四周到达这个节点，两边+了一步变成2~3步的个数。然后再加上和下边界1步的个数 
1
2
3
4
5
6
7
8
9
10
11
12
13
def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:
    dp = [[0]*n for _ in range(m)]
    for _ in range(N):
    # deep copy of dp
        t = [s[:] for s in dp]
        for x in range(m):
            for y in range(n):
                a = t[x-1][y] if x > 0 else 1
                b = t[x+1][y] if x + 1 < m else 1
                c = t[x][y-1] if y > 0 else 1
                d = t[x][y+1] if y + 1 < n else 1
                dp[x][y] = a + b + c + d
    return dp[i][j] % (10**9+7)

688. Knight Probability in Chessboard

中国象棋的马，在棋盘上走K步，问还在棋盘上的概率。原题

方法一：和576一样。区别在于刚好K步，走法不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
    directions = ((-1, -2), (-2, -1), (-2, 1), (-1, 2),
                  (1, -2), (2, -1), (2, 1), (1, 2))
    
    dp = [[0]*N for _ in range(N)]
    dp[r][c] = 1
    for k in range(K):
        new_dp = [[0]*N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                new_dp[i][j] = sum(dp[i+di][j+dj] for di, dj in directions
                                   if 0<=i+di<N and 0<=j+dj<N)
        dp = new_dp
    return sum(sum(dp, [])) / (8**K)

方法二：少了最后一步求和的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
    directions = ((-1, -2), (-2, -1), (-2, 1), (-1, 2),
                  (1, -2), (2, -1), (2, 1), (1, 2))
    
    dp = [[0]*N for _ in range(N)]
    dp[r][c], out = 1, 0
    for k in range(K):
        new_dp = [[0]*N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                for di, dj in directions:
                    if 0<=i+di<N and 0<=j+dj<N:
                        new_dp[i+di][j+dj] += dp[i][j] / 8
                    else:
                        out += dp[i][j] / 8
        dp = new_dp
    return 1 - out

132. Palindrome Partitioning II

最少需要多少次分割，可以将s切成的每段都是回文串。原题

1
2
3
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

方法一：比较暴力的方法。

1
2
3
4
5
6
7
8
9
def minCut(self, s: str) -> int:
    n = len(s)
    cut = list(range(n))
    for i in range(1, n):
        if s[:i+1] == s[:i+1][::-1]:
            cut[i] = 0
            continue
        cut[i] = min(cut[j]+1 for j in range(i) if s[j+1:i+1]==s[j+1:i+1][::-1])
    return cut[-1]

1043. Partition Array for Maximum Sum

将一个数组切分， 每段可以把所有的值变成当前段最大值。每段最长不能超过k。求切分后所有数的最大的和。原题

1
2
3
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]

方法一：稍微想一想就想到了dp。这个AC的方法将近3s了。不过也beats了20%。索引那里需要注意是从1开始的，切片的时候得减去。

1
2
3
4
5
6
7
8
def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
    n = len(A)
    dp = [0] * (n+1)
    for i, a in enumerate(A, 1):
        for j in range(1, K+1):
            if i-j >= 0:
                dp[i] = max(dp[i], dp[i-j] + max(A[i-j:i])*j)
    return dp[-1]
方法二：优化一下，768ms, beats 50%了。最大值可以不用每次都算，索引改从0开始了，从1开始某些地方太让人困惑。 
1
2
3
4
5
6
7
8
9
10
11
12
def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
    n = len(A)
    dp = [0] * (n+1)
    for i, a in enumerate(A):
        r = a
        for j in range(1, K+1):
            r = max(r, A[i-j+1] if i-j+1>=0 else 0)
            if i-j+1 >= 0:
                dp[i+1] = max(dp[i+1], dp[i-j+1] + r*j)
            else:
                break
    return dp[-1]
方法三：Lee的方法和我一样，在循环边界上更加整洁。 
1
2
3
4
5
6
7
8
9
def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
    n = len(A)
    dp = [0] * (n+1)
    for i, a in enumerate(A):
        r = a
        for j in range(1, min(i+1, K)+1):
            r = max(r, A[i-j+1])
            dp[i+1] = max(dp[i+1], dp[i-j+1] + r*j)
    return dp[-1]

790. Domino and Tromino Tiling

在2*N的平台上摆放两种多米诺骨牌，一共有多少种摆法。原题

1
2
3
4
5
6
7
Example:
Input: 3
Output: 5
Explanation: 
The five different ways are listed below, different letters indicates different tiles:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY

方法一：这题看了答案，自己推的状态方程不太对。没考虑第2种骨牌的多种摆法。引用一张高票的手写推导图。

1
2
3
4
5
dp[n]=dp[n-1]+dp[n-2]+ 2*(dp[n-3]+...+d[0])
=dp[n-1]+dp[n-2]+dp[n-3]+dp[n-3]+2*(dp[n-4]+...+d[0])
=dp[n-1]+dp[n-3]+(dp[n-2]+dp[n-3]+2*(dp[n-4]+...+d[0]))
=dp[n-1]+dp[n-3]+dp[n-1]
=2*dp[n-1]+dp[n-3]
1
2
3
4
5
6
def numTilings(self, N: int) -> int:
    mod = 10**9 + 7
    dp = [0, 1, 2, 5]
    for i in range(4, N+1):
        dp.append(2*dp[i-1] + dp[i-3])
    return dp[-1]%mod if N>3 else dp[N]

329. Longest Increasing Path in a Matrix

矩阵中最长的递增路径。原题

1
2
3
4
5
6
7
8
Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

方法一：回溯+记忆化搜索。这题做的时候状态不太好，导致好几次WA和超时。首先要明白几点。因为是递增，不包含重复的，所以不需要对已遍历的节点进行重复判断。对于每个点来说，它所能延长到最长的路径是一定的。所以当得到这个值之后，后续再到这个节点就无需再计算了。使用一个字典来记录它的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def longestIncreasingPath(self, g: List[List[int]]) -> int:
    if not g: return 0
    m, n = len(g), len(g[0])
    
    seen = {}
    
    def spread(i, j, p):
        if (i, j) in seen: return seen[(i, j)]
        p.append(g[i][j])
        
        nxt = 0
        for x, y in ((i+1, j), (i, j+1), (i-1, j), (i, j-1)):
            if 0<=x<m and 0<=y<n:
                if g[x][y] > p[-1]:
                    nxt = max(nxt, spread(x, y, p))
        ans = 1 + nxt
        seen[(i, j)] = ans
        p.pop()
        return ans
                    
    for i in range(m):
        for j in range(n):
            spread(i, j, [])
    return max(seen.values())
方法二：这题先入为主了，矩阵中的路径老想着回溯。其实dfs就行了，参数p除了比较根本没用。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longestIncreasingPath(self, g: List[List[int]]) -> int:
    if not g: return 0
    m, n = len(g), len(g[0])
    
    def dfs(i, j):
        if not dp[i][j]:
            val, ans = g[i][j], 0
            for x, y in ((i+1, j), (i, j+1), (i-1, j), (i, j-1)):
                if 0<=x<m and 0<=y<n and val < g[x][y]:
                    ans = max(ans, dfs(x, y))
            dp[i][j] = 1 + ans
        return dp[i][j]
    
    dp = [[0] * n for _ in range(m)]
    return max(dfs(i, j) for i in range(m) for j in range(n))

638. Shopping Offers

这题和329差不多的方法。说商店有东西打折。一些商品打包打折卖。给定每种东西的数量，问最少需要多少钱。最多只有6个商品，每样不超过6个。你不能多买，即便需要的钱更少。原题

1
2
3
4
5
6
7
Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation: 
There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

方法一：思路还算清晰，但是这里因为自作聪明加了两行代码，导致最后严重超时。方法还是dfs + 记忆化。因为加了注释中的代码，这里原本想的是，索性将原价商品页当做打包卖，只不过价格不一样而已。但是这样会增加dfs中的m。最后导致了超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
    n = len(price)
    # for i in range(n):
    #     special.append([int(i==j) for j in range(n)] + [price[i]])
    m = len(special)
    memo = {}
    
    def dfs(*needs):
        if needs in memo: return memo[needs]
        if all(need==0 for need in needs):
            return 0
        ans = sum(need*p for need, p in zip(needs, price))
        for j in range(m):
            left = [cn-a for cn, a in zip(needs, special[j][:-1])]
            if all(l>=0 for l in left) and ans > special[j][-1]:
                ans = min(ans, special[j][-1] + dfs(*left))
        memo[needs] = ans
        return ans
        
    return dfs(*needs)
方法二：优化方法一，删除一些没用的变量。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
    memo = {}
    
    def dfs(*needs):
        if needs in memo: return memo[needs]
        ans = sum(need*p for need, p in zip(needs, price))
        for spec in special:
            left = [cn-a for cn, a in zip(needs, spec[:-1])]
            if min(left)>=0 and ans > spec[-1]:
                ans = min(ans, spec[-1] + dfs(*left))
        memo[needs] = ans
        return ans
        
    return dfs(*needs)

152. Maximum Product Subarray

最大的子数组乘积。和1567题目类似，那题是求长度，可以贪心，这题没有。原题

1
2
3
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

方法一：dp写法和1567dp解法相似。[-2]的例子只需要在前面判断一下长度是否为1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
def maxProduct(self, nums: List[int]) -> int:
    ans, n = float('-inf'), len(nums)
    if n == 1: return nums[0]
    pos, neg = [0]*n, [0]*n
    for i, num in enumerate(nums):
        if num > 0:
            pos[i] = num * (pos[i-1] if pos[i-1]!=0 else 1)
            neg[i] = num * (neg[i-1])
        elif num < 0:
            pos[i] = num * (neg[i-1])
            neg[i] = num * (pos[i-1] if pos[i-1]!=0 else 1)
        ans = max(ans, pos[i], neg[i])
    return ans
方法二：本来方法一也是和lee的1567解法写的。寻思这回不能差太多吧。啊这。。不知道怎么证明，但是看着答案就能想明白，最大值一定存在于这两个数组中。 
1
2
3
4
5
6
def maxProduct(self, A: List[int]) -> int:
    B = A[::-1]
    for i in range(1, len(A)):
        A[i] *= A[i - 1] or 1
        B[i] *= B[i - 1] or 1
    return max(A + B)
方法三：改了一个生成器写法。 
1
2
3
4
5
def maxProduct(self, A: List[int]) -> int:
    def count(x, y):
        return (x or 1) * y
    A, B = itertools.accumulate(A, count), itertools.accumulate(A[::-1], count)
    return max(itertools.chain(A, B))

LCP 20. 快速公交

有这么个站点，每次从站点网下走需要inc时间，往回走需要dec时间，可以通过乘坐i公交车从移动到jum[i]*x站点，耗时为cost[i]，问到达target站点最少需要多少时间。

1
2
3
4
5
6
7
8
9
10
11
12
输入：target = 612, inc = 4, dec = 5, jump = [3,6,8,11,5,10,4], cost = [4,7,6,3,7,6,4]

输出：26

解释：
小扣步行至 1 号站点，花费时间为 4；
小扣从 1 号站台搭乘 0 号公交至 3 * 1 = 3 站台，花费时间为 4；
小扣从 3 号站台搭乘 3 号公交至 11 * 3 = 33 站台，花费时间为 3；
小扣从 33 号站台步行至 34 站台，花费时间为 4；
小扣从 34 号站台搭乘 0 号公交至 3 * 34 = 102 站台，花费时间为 4；
小扣从 102 号站台搭乘 1 号公交至 6 * 102 = 612 站台，花费时间为 7；
最终小扣花费总时间为 26。

方法一：记忆化搜索了。杯赛时没做出来。不好想的地方在12行，往回退的时候。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:

    @lru_cache(None)
    def dp(i):
        if i == 0: return 0
        if i == 1: return inc
        ans = i * inc
        for bus, times in enumerate(jump):
            j, mod = divmod(i, times)
            ans = min(ans, mod*inc + cost[bus] + dp(j))
            if mod:
                ans = min(ans, (times-mod)*dec + cost[bus] + dp(j+1))
        return ans

    return dp(target) % (10**9+7)

877. Stone Game

石头游戏，一共有偶数堆，并且总数为奇数。每次拿左或者右的一堆，每次拿都是最优解，问Alex先拿能否赢。原题

1
2
3
4
5
6
7
8
Input: piles = [5,3,4,5]
Output: true
Explanation: 
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.

方法一：还算简单的一个dp，488ms, beats40%。内存有点多120多M。思路是从两边到中间。

1
2
3
4
5
6
7
8
def stoneGame(self, piles: List[int]) -> bool:
    
    @lru_cache(None)
    def dp(i, j):
        if i == j:
            return 0
        return max(piles[i] + dp(i+1, j), piles[j] + dp(i, j-1))
    return dp(0, len(piles)-1)
方法二：迭代，不会用那么多的空间20M。不过过程不好想，从哪里开始，d表示段的长度，从最小的段开始。这里用了减法表示dp[i][j] 在piles[i]~piles[j]之间能领先多少。 
1
2
3
4
5
6
7
8
9
def stoneGame(self, p: List[int]) -> bool:
    n = len(p)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = p[i]
    for d in range(1, n):
        for i in range(n - d):
            dp[i][i+d] = max(p[i]-dp[i+1][i+d], p[i+d]-dp[i][i+d-1])
    return dp[0][-1] > 0
方法三：一维空间实现。这个方法好难想，dp[i] 表示以i为起点d为长度堆 也就是piles[i:i+d]最多能赢对手多少。 
1
2
3
4
5
6
7
8
def stoneGame(self, p: List[int]) -> bool:
    n = len(p)
    dp = p[:]
    for d in range(1, n):
        for i in range(n - d):
            # print(i, d, dp, p[i]-dp[i+1], p[i+d]-dp[i])
            dp[i] = max(p[i] - dp[i + 1], p[i + d] - dp[i])
    return dp[0] > 0

以[5,3,4,5]输出i, d ，dp是这样的。

1
2
3
4
5
6
0 1 [5, 3, 4, 5] 2 -2
1 1 [2, 3, 4, 5] -1 1
2 1 [2, 1, 4, 5] -1 1
0 2 [2, 1, 1, 5] 4 2
1 2 [4, 1, 1, 5] 2 4
0 3 [4, 4, 1, 5] 1 1

方法四：对于此题来说，堆为偶数个，和为奇数。那么将其分为两组，奇数索引组合偶数索引组，假设这两个人都按照这个拿，Alex先手总能拿到多的那个。因为Alex可以保证拿到多的那组，比如[5,3,4,5]奇数组的5+4>5+3，那么在拿走第一个5，对手只能从两个偶数组选，而无论对手选哪个偶数，Alex总有下一个奇数组的数可选。这题曾经在知乎上看到过uwi在比赛中思考了1分多钟就写出了这样的答案，不愧为常年霸榜的选手。

1
2
def stoneGame(self, p: List[int]) -> bool:
    return True

1690. Stone Game VII

此题和877题相似，区别在于拿取一个石头得分为剩余石头的总和。

1
2
3
4
5
6
7
8
9
Input: stones = [5,3,1,4,2]
Output: 6
Explanation: 
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.

方法一：此题竞赛没过，写了递归的超时了，迭代的状态转移方程没有找到。但是将lru_cache最大长度改为1000就能过，耗时6000ms。就很迷

1
2
3
4
5
6
7
8
9
10
11
12
def stoneGameVII(self, stones: List[int]) -> int:
    total = sum(stones)

    @lru_cache(1000)
    def dp(i, j, remain):
        # print(i, j, remain)
        if i == j:
            return 0
        return max(remain-stones[i]-dp(i+1, j, remain-stones[i]),
                   remain-stones[j]-dp(i, j-1, remain-stones[j]))

    return dp(0, len(stones)-1, total)

方法二：remain是冗余的，这个比赛时没有想好。这个方法lru_cache(None)同样过不了。

1
2
3
4
5
6
7
8
9
10
11
12
def stoneGameVII(self, stones: List[int]) -> int:
    total = sum(stones)
    p = list(accumulate([0]+stones))

    @lru_cache(1000)
    def dp(i, j):
        if i == j:
            return 0
        return max(p[j+1]-p[i+1]-dp(i+1, j),
                   p[j]-p[i]-dp(i, j-1))

    return dp(0, len(stones)-1)

方法三：迭代。这里想错了一件事情，dp[i][j]表示stones[i]~stones[j]最多的得分是多少。而不是stones[i]开始j长度最多的得分，这里将j和d搞混了。

1
2
3
4
5
6
7
8
9
10
def stoneGameVII(self, stones: List[int]) -> int:
    n = len(stones)
    p = list(accumulate([0]+stones))
    dp = [[0]*n for _ in range(n)]
    for d in range(1, n):
        for i in range(n-d):
            j = i + d
            dp[i][j] = max(p[j+1]-p[i+1]-dp[i+1][j],
                           p[j]-p[i]-dp[i][j-1])
    return dp[0][-1]

300. Longest Increasing Subsequence

最长的递增子序列长度。

1
2
3
Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

方法一：首次AC的方法，时间O(n^2)。

1
2
3
4
5
6
7
8
9
def lengthOfLIS(self, nums: List[int]) -> int:
    # dp[i] means the ans of nums[:i]
    n = len(nums)
    dp = [1] * (n+1)
    for i in range(1, n):
        for j in range(i)[::-1]:
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return nums and max(dp) or 0
方法二：看了follow up: 有N*(logN)的方法，那么就往二分法和堆上想。这个二分法太难想了，创了一个缓冲数组用来记录当前的子序列。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def lengthOfLIS(self, nums: List[int]) -> int:
    tails = [0] * len(nums)
    size = 0
    for num in nums:
        print(tails)
        lo, hi = 0, size
        while lo < hi:
            mid = (lo+hi) // 2
            if tails[mid] < num:
                lo = mid + 1
            else:
                hi = mid
        tails[lo] = num
        size = max(lo+1, size)
    return size

假设输入是[10,9,2,5,3,7,101,18,-1,0,1]，tails这样变化，当出现一个较小的数，找到位置并替换，这样tails有效的部分还是有序的。

1
2
3
4
5
6
7
8
9
10
11
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[2, 3, 7, 0, 0, 0, 0, 0, 0, 0, 0]
[2, 3, 7, 101, 0, 0, 0, 0, 0, 0, 0]
[2, 3, 7, 18, 0, 0, 0, 0, 0, 0, 0]
[-1, 3, 7, 18, 0, 0, 0, 0, 0, 0, 0]
[-1, 0, 7, 18, 0, 0, 0, 0, 0, 0, 0]
方法三：方法二的简写。 
1
2
3
4
5
6
def lengthOfLIS(self, nums: List[int]) -> int:
    dp = []
    for num in nums:
        i = bisect.bisect_left(dp, num)
        dp[i:i+1] = [num]
    return len(dp)

673. Number of Longest Increasing Subsequence

求最长递增子序列的个数。和300很像，基于300上进行修改。

方法一：基于300方法一进行修改，dp元素保存两个信息，一个是最大长度，一个是数量。思考的时候要想如果dp[-1][-1]不能直接求得值的话，要考虑重新遍历一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
def findNumberOfLIS(self, nums: List[int]) -> int:
    n, longest = len(nums), 1
    dp = [[1, 1] for _ in range(n)]
    for i in range(1, n):
        cur_long = 1
        c = collections.defaultdict(int)
        for j in range(i):
            if nums[i] > nums[j]:
                c[dp[j][0]] += dp[j][1]
                cur_long = max(cur_long, dp[j][0] + 1)
        dp[i] = [cur_long, max(c[cur_long-1], 1)]
        longest = max(longest, cur_long)
    return sum(cnt for l, cnt in dp if l==longest)

方法二：进行了一些优化。比方法一快了300ms，写完之后和评论区方法比较，明明是一样的，不知道为啥慢了100ms，后来一行一行代码进行替换，调了半天，发现注释部分的代码要慢100ms，刷新了我的认知，为什么数组下标取值会慢这么多？这也太玄学了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findNumberOfLIS(self, nums: List[int]) -> int:
    n, max_for_all = len(nums), 1
    dp = [[1, 1] for _ in range(n)]
    for i, num in enumerate(nums):
        max_len, count = 1, 0
        for j in range(i):
            # if nums[j] < nums[i]:
            if nums[j] < num:
                if dp[j][0] + 1 > max_len:
                    max_len = dp[j][0] + 1 
                    count = 0
                if dp[j][0] == max_len - 1:
                    count += dp[j][1]
        dp[i] = [max_len, max(count, dp[i][1])]
        max_for_all = max(max_len, max_for_all)
    return sum([item[1] for item in dp if item[0] == max_for_all])
方法三：这题最好的方法还是二分法。dp[i][x]表示长度为i的子序列以x结尾的有多少个。 
1
2
3
4
5
6
7
8
9
10
11
12
def findNumberOfLIS(self, nums: List[int]) -> int:
    dp = collections.defaultdict(collections.Counter)
    dp[-1][float('-inf')] = 1
    seq = []
    for num in nums:
        i = bisect.bisect_left(seq, num)
        if i == len(seq):
            seq.append(num)
        else:
            seq[i] = num
        dp[i][num] += sum(dp[i-1][end] for end in dp[i-1] if end < num)
    return sum(dp[max(0, len(seq)-1)].values())

面试题 17.08. 马戏团人塔

300的变种，比较两个维度。说人可以叠罗汉，但是只能将高度和体重都大的人放在下面。

方法一：这题测试用例n^2的写法过不了。这题比堆箱子简单一点。将高度升序排列，体重降序排列。就可以按照体重来求最长上升子序列了。体重降序可以避免了高度相同的人导致结果错误。评论区学了一个方法。

1
2
3
4
5
6
输入样例:[[4,5],[4,6],[6,7],[2,3],[1,1]]
先按升高升序排列,再按体重升序排列
>>>:[1, 1],[2, 3],[4, 5],[4, 6],[6, 7]
>>>answer = 5
先按升高升序排列,再按体重降序排列
>>>:[1, 1],[2, 3],[4, 6],[4, 5],[6, 7]
1
2
3
4
5
6
def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
    dp=[]
    for a, b in sorted(zip(height, weight), key=lambda x:(x[0],-x[1])):
       pos = bisect.bisect_left(dp, b)
       dp[pos:pos+1] = [b]
    return len(dp)

面试题 08.13. 堆箱子

这题和300题很像，是一个变种题。要把长宽高都大的放在底层，问最多可以叠多高。

方法一：和300一样，但是要排序，因为箱子可以随便选，这里有点迷，我一直没有想明白为什么zip会超时，而直接数组比较就不会超时。我想了想300题的NlogN的解法，但在此题上并不适用。

1
2
3
4
5
6
7
8
9
10
11
def pileBox(self, box: List[List[int]]) -> int:
    n = len(box)
    box.sort()
    dp = [0] * n
    for i in range(n):
        dp[i] = box[i][-1]
        for j in range(i):
            # if all(b > t for b, t in zip(box[i], box[j])):
            if box[j][0]<box[i][0] and box[j][1]<box[i][1] and box[j][2]<box[i][2]:
                dp[i] = max(dp[i], dp[j] + box[i][-1])
    return max(dp)

方法二：sort时以长度升序，宽度降序。这样比较的时候可以不用比较长度了，降序是为了适应长度相等的情况。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def pileBox(self, box: List[List[int]]) -> int:
        n = len(box)
        box.sort(key=lambda x: (x[0], -x[1]))
        dp = [0] * n
        for i in range(n):
            dp[i] = box[i][-1]
            for j in range(i):
                if box[j][1]<box[i][1] and box[j][2]<box[i][2]:
                    dp[i] = max(dp[i], dp[j] + box[i][-1])
        return max(dp)

1594. Maximum Non Negative Product in a Matrix

最大的从左上到右下的乘积。

方法一：这题想着迭代方法，竞赛的时候差了一行代码，时间就到了。递归的思路好想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxProductPath(self, g: List[List[int]]) -> int:
    mod = 10**9 + 7
    M, N = len(g), len(g[0])
    
    @lru_cache(None)
    def dp(i, j):
        if i==0 and j==0: return g[0][0], g[0][0]
        if i<0 or j<0: return float('-inf'), float('inf')
        if g[i][j] == 0: return 0, 0
        mx1, mn1 = dp(i-1, j)
        mx2, mn2 = dp(i, j-1)
        mx, mn = max(mx1, mx2)*g[i][j], min(mn1, mn2)*g[i][j]
        return (mx, mn) if g[i][j]>0 else (mn, mx)
    
    mx, _ = dp(M-1, N-1)
    return mx % mod if mx>=0 else -1

方法二：迭代的初识值没想好，想着赋值成(g[0][0], float('inf'))了，实际上(g[0][0], g[0][0])就对了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maxProductPath(self, g: List[List[int]]) -> int:
    mod = 10**9 + 7
    M, N = len(g), len(g[0])
    default = (float('-inf'), float('inf'))
    dp = [[default]*N for _ in range(M)]
    dp[0][0] = (g[0][0], g[0][0])
    for i in range(M):
        for j in range(N):
            if i==0 and j==0: continue
            cur = g[i][j]
            if cur == 0:
                dp[i][j] = 0, 0
                continue
            mx1, mn1 = dp[i-1][j] if i else default
            mx2, mn2 = dp[i][j-1] if j else default
            mx, mn = max(mx1, mx2)*cur, min(mn1, mn2)*cur
            dp[i][j] = (mx, mn) if cur>0 else (mn, mx)
    return dp[-1][-1][0] % mod if dp[-1][-1][0]>=0 else -1

面试题 08.14. 布尔运算

给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。

1
2
3
4
5
6
输入: s = "1^0|0|1", result = 0

输出: 2
解释: 两种可能的括号方法是
1^(0|(0|1))
1^((0|0)|1)

方法一：我开始想的是将0，1的个数都分别计算。但是效率却不高。时间只beats5%。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def countEval(self, s: str, result: int) -> int:

    @lru_cache(None)
    def dfs(q):
        n = len(q)
        if n==1:
            return (0, 1) if q=='1' else (1, 0)
        ans = [0, 0]
        for i in range(1, n, 2):
            # l_zero, l_one = dfs(q[:i])
            # r_zero, r_one = dfs(q[i+1:])
            # ans[eval('0{}1'.format(q[i]))] += l_zero*r_one
            # ans[eval('0{}0'.format(q[i]))] += l_zero*r_zero
            # ans[eval('1{}0'.format(q[i]))] += l_one*r_zero
            # ans[eval('1{}1'.format(q[i]))] += l_one*r_one
            left, right = dfs(q[:i]), dfs(q[i+1:])
            for (l_v, l_c), (r_v, r_c) in itertools.product(enumerate(left), enumerate(right)):
                ans[eval('{}{}{}'.format(l_v, q[i], r_v))] += l_c * r_c
        return ans

    return dfs(s)[result]

方法二：根据评论区的方法，找到自己方法的性能瓶颈。在于大量的创建字符串执行eval，将这里改为字典映射后，从500ms减少为90ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def countEval(self, s: str, result: int) -> int:

    @lru_cache(None)
    def dfs(q):
        n = len(q)
        ans = [0, 0]
        if n==1:
            ans[int(q)] += 1
            return ans
        for i in range(1, n, 2):
            left, right = dfs(q[:i]), dfs(q[i+1:])
            for (l_v, l_c), (r_v, r_c) in itertools.product(enumerate(left), enumerate(right)):
                ans[ops[q[i]](l_v, r_v)] += l_c * r_c
        return ans
    ops = {'|': or_, '^': xor, '&': and_}
    return dfs(s)[result]

面试题 17.13. 恢复空格

你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子”I reset the computer. It still didn’t boot!”已经变成了”iresetthecomputeritstilldidntboot”。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

方法一：特别慢，虽然ac了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def respace(self, dictionary: List[str], sentence: str) -> int:
        dic = set(dictionary)
        max_len = len(max(dictionary, key=len))

        @lru_cache(None)
        def dfs(s):
            # print(s)
            if not s: return 0
            ans = float('inf')
            for i in range(1, min(len(s), max_len)+1):
                right = dfs(s[i:])
                if s[:i] in dic:
                    ans = min(ans, right)
                else:
                    ans = min(ans, i + right)
            return ans

        return dfs(sentence)
方法二：从头开始匹配这样就快了只要300ms 
1
2
3
4
5
6
7
8
9
10
11
12
13
def respace(self, dictionary: List[str], sentence: str) -> int:
    dic, N = set(dictionary), len(sentence)
    lens = {len(w) for w in dictionary}

    @lru_cache(None)
    def dfs(i):
        if i >= N:
            return 0
        tails = [dfs(i+d) for d in lens if i+d<=N and sentence[i:i+d] in dic]
        tails.append(1 + dfs(i+1))
        return min(tails, default=0)

    return dfs(0)
方法三：dp的迭代写法。260ms 
1
2
3
4
5
6
7
8
9
10
11
def respace(self, dictionary: List[str], sentence: str) -> int:
    dic, N = set(dictionary), len(sentence)
    lens = {len(w) for w in dictionary}
    dp = [0]+ [float('inf')]*N # dp[i]表示前sentence[:i]未识别的字符数
    for i in range(1, N+1):
        dp[i] = dp[i-1] + 1
        dp[i] = min([dp[i]]+[dp[i-d] 
            for d in lens if sentence[i-d:i] in dic and i>=d]
        )
    # print(dp)
    return dp[-1]

1611. Minimum One Bit Operations to Make Integers Zero

最少需要多少步能将数变成0。两种操作方式，一种翻转最低位的数字。一种是找到x100..00（n个0,n可以=0）的x位翻转。

方法一：这题竞赛时想了个七七八八，还是没写出来。总体来说此题不难，比第3题简单。

分为这样的步骤。1XXXXXXX -> 11000000 -> 10000000 -> 0

1XXXXXX -> 1100000 needs minimumOneBitOperations(1XXXXXX ^ 1100000), 这步没有想明白，可以递归，因为想让1XXXXXX ^ 1100000 == 0，就只能让 1XXXXXX变为1100000 。所以这里是等价的。

1100000 -> 100000 needs 1 operation.
100000 -> 0, where 100000 is 2^k, needs 2^(k-1) - 1 operations.

1
2
3
4
5
6
7
8
9
class Solution:
    dp = {0: 0}
    def minimumOneBitOperations(self, n: int) -> int:
        if n not in self.dp:
            b = 1
            while (b<<1) <= n:
                b <<= 1
            self.dp[n] = self.minimumOneBitOperations((b>>1) ^ b ^ n) + 1 + b - 1
        return self.dp[n]

1027. Longest Arithmetic Subsequence

最长的等差子序列长度。

1
2
3
4
Input: A = [9,4,7,2,10]
Output: 3
Explanation: 
The longest arithmetic subsequence is [4,7,10].

方法一：O(N^2)的方法。时间beats80%, 2.6s。这里试了一下ans = max([ans] + list(dp[i].values())) 居然要4s多。Lee这里使用了一个tuple作为key，但是要慢一点，3s。

1
2
3
4
5
6
def longestArithSeqLength(self, A: List[int]) -> int:
    dp = defaultdict(lambda : defaultdict(lambda : 1))
    for i, a in enumerate(A):
        for j, b in enumerate(islice(A, i)):
            dp[i][a-b] = dp[j][a-b] + 1
    return max(max(dp[i].values()) for i in range(len(A)))

416. 分割等和子集

能否将数组分为两个和相等的子数组。经典的0-1背包问题。

方法一：看了题解做上的，主要没想到怎么将它转化为背包问题的。它其实等价于从数组中选出一些数字，使得这些数的和为数组和的一半。

1
2
3
4
5
6
7
8
9
10
def canPartition(self, nums: List[int]) -> bool:
    s, N = sum(nums), len(nums)
    if s&1 or N<2:
        return False
    target = s // 2
    dp = [[False]*(target+1) for _ in range(N)] # dp[i][j]表示nums[:i]的元素能否组成和恰好为j
    for i, a in enumerate(nums):
        for j in range(target+1):
            dp[i][j] = a==j or dp[i-1][j] or (j>=a and dp[i-1][j-a])
    return dp[-1][-1]

方法二：方法一空间优化。正序会对结果造成影响，导致计算错误。

1
2
3
4
5
6
7
8
9
10
def canPartition(self, nums: List[int]) -> bool:
    s, N = sum(nums), len(nums)
    if s&1 or N<2:
        return False
    target = s // 2
    dp = [False] * (target+1)
    for i, a in enumerate(nums):
        for j in range(target+1)[::-1]:
            dp[j] = a==j or dp[j] or (j>=a and dp[j-a])
    return dp[-1]
方法三：同样的原理，但是使用位运算来保存结果。速度是前两种的30倍！！bool(mask>>k & 1)表示是否可以组成和为k。python得益于int没有长度限制，所以不用转成数组的形式。 
1
2
3
4
5
6
7
8
def canPartition(self, nums: List[int]) -> bool:
    s, N = sum(nums), len(nums)
    if s&1 or N<2: return False
    target = s // 2
    mask = 1
    for num in nums:
        mask |= mask<<num
    return bool(mask>>target & 1)

方法四：可以写成一行，评论中大神的写法和我的写法。

1
2
3
def canPartition(self, nums: List[int]) -> bool:
    return 1-sum(nums)%2 == reduce(lambda x, y: x | (x<<y), nums, 1) >> (sum(nums))//2 & 1
    # return not sum(nums)&1 and bool(reduce(lambda x, y: x | (x<<y), nums, 1) >> (sum(nums))//2 & 1)

128. Longest Consecutive Sequence

求数组中最长的连续序列，可以打乱顺序。要求时间复杂度O(n)。

1
2
3
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

方法一：Union-Find。没想到能用并查集来求，看了标签提示才恍然大悟。一开始写错了，把num和num-1也相连了，这样1和3就被连到了一起，注意一下空输入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longestConsecutive(self, nums: List[int]) -> int:
    def union(x, y):
        uf[find(x)] = find(y)

    def find(x):
        uf.setdefault(x, x)
        if x != uf[x]:
            uf[x] = find(uf[x])
        return uf[x]

    uf = {}

    for num in nums:
        union(num, num+1)
    
    return nums and Counter(find(x) for x in set(nums)).most_common(1)[0][1] or 0
方法二：动态规划。这个方法非常好，我记得Lee215好像用过，我一时想不起来是哪道题了。 
1
2
3
4
5
6
7
8
9
def longestConsecutive(self, nums: List[int]) -> int:
    d, ans = defaultdict(int), 0
    for num in nums:
        if not d[num]:   # 这里不能使用 if num not in d，因为再找最右时可能会更新d[num-1]为0
            left, right = d[num-1], d[num+1]
            d[num] = left + right + 1
            d[num-left] = d[num+right] = d[num]
            ans = max(ans, d[num])
    return ans
方法三：by@stefan。时间O(n)，因为只对比了开头。每个数字只遍历一次。 
1
2
3
4
5
6
7
8
9
10
def longestConsecutive(self, nums: List[int]) -> int:
    nums = set(nums)
    best = 0
    for x in nums:
        if x - 1 not in nums:  # 如果x是一段连续数字的开头
            y = x + 1
            while y in nums:
                y += 1
            best = max(best, y - x)
    return best

1314. Matrix Block Sum

矩阵块的求和。原题

1
2
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

方法一：竞赛时暴力法过的。这里实际上求和时可以利用之前的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    dp = [list(itertools.accumulate(row)) for row in mat]
    dp = [list(itertools.accumulate(row)) for row in zip(*dp)]        
    dp = list(zip(*dp))
    ans = []
    for i in range(m):
        tmp = []
        for j in range(n):
            r_lo, r_hi = max(0, i-k), min(i+k, m-1)
            c_lo, c_hi = max(0, j-k), min(j+k, n-1)
            cur_sum = dp[r_hi][c_hi]
            if r_lo > 0:
                cur_sum -= dp[r_lo-1][c_hi]
            if c_lo > 0:
                cur_sum -= dp[r_hi][c_lo-1]
            if r_lo > 0 and c_lo > 0:
                cur_sum += dp[r_lo-1][c_lo-1]
            tmp.append(cur_sum)
        ans.append(tmp)
    return ans

1738. Find Kth Largest XOR Coordinate Value

找到矩阵中第K大的值，值是指坐标(a,b)所有妈祖0<=i<=a<m，0<=j<=b<n条件的异或和。

1
2
3
Input: matrix = [[5,2],[1,6]], k = 1
Output: 7
Explanation: The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.

方法一：dp，和1314很像。比赛时没有时间做。

1
2
3
4
5
6
7
8
9
10
11
12
def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
    M, N = len(matrix), len(matrix[0])
    g = [[0] * (N+1) for _ in range(M+1)]        
    heap = []
    for i in range(1, M+1):
        for j in range(1, N+1):
            g[i][j] = matrix[i-1][j-1] ^ g[i-1][j-1] ^ g[i-1][j] ^ g[i][j-1]
            if len(heap) < k:
                heapq.heappush(heap, g[i][j])
            elif g[i][j] > heap[0]:
                heapq.heapreplace(heap, g[i][j])
    return heap[0]

1626. Best Team With No Conflicts

有这样一个球队，每个人有一个自己的得分。当一个团队中有一个年轻的球员是比自己年长球员分多时，这两个球员就会打架。所以为了避免这样的情况，选出一个最大得分的团队，问得分是多少。

1
2
3
4
5
6
Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: It is best to choose the first 3 players. 
Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.

方法一：这题因为竞赛时卡在第二题上，所以没有时间来做了。和俄罗斯套娃问题很像。当球员按照年龄，得分排好序后。问题转化为了一个最长上升子序列和的问题。时间复杂度是O(n^2)。

1
2
3
4
5
6
7
8
9
10
def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
    p = sorted(zip(ages, scores))
    n, ans = len(p), 0
    dp = [0] * n
    for i in range(len(p)):
        dp[i] = p[i][1]
        for j in range(i):
            if p[i][1] >= p[j][1]:
                dp[i] = max(dp[i], dp[j]+p[i][1])
    return max(dp)

823. Binary Trees With Factors

给你一些大于1的数，要求用这些数组成一个树，树的父节点为两个子节点的乘积。问有多少种组成方式。

1
2
3
Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

方法一：很容易想到dp，以每个点为父节点，看组成子节点的组合有多少种，然后相乘。400ms

1
2
3
4
5
6
7
8
9
10
11
def numFactoredBinaryTrees(self, A: List[int]) -> int:
    mod = 10**9 + 7
    N = len(A)
    s_nums = set(A)
    dp = {n: 1 for n in s_nums}
    nums = sorted(s_nums)
    for i, n in enumerate(nums):
        for j in range(i):
            if n%nums[j]==0 and n//nums[j] in s_nums:
                dp[n] += dp[nums[j]] * dp[n//nums[j]]
    return sum(dp.values()) % mod
方法二：这里容易想到一个优化，当左右子树节点不同时，可以通过互换的方式来增加；那么也就是说找左右子节点时，因为这里将其排了序，所以左子节点<=右子节点。运行时间减少为原来的一半还少。144ms

1
2
3
4
5
6
7
8
9
10
11
12
def numFactoredBinaryTrees(self, A: List[int]) -> int:
    mod = 10**9 + 7
    N = len(A)
    s_nums = set(A)
    dp = {n: 1 for n in s_nums}
    nums = sorted(s_nums)
    for i, n in enumerate(nums):
        for j in range(i):
            if nums[j] > sqrt(n): break
            if n%nums[j]==0 and n//nums[j] in s_nums:
                dp[n] += (dp[nums[j]] * dp[n//nums[j]]) * (1+(nums[j]!=n//nums[j]))
    return sum(dp.values()) % mod

方法三：Lee的写法。但是运行时间比方法一略优，时间相当于方法二的2倍。336ms

1
2
3
4
5
def numFactoredBinaryTrees(self, A: List[int]) -> int:
    dp = {}
    for a in sorted(A):
        dp[a] = sum(dp[b] * dp.get(a//b, 0) for b in dp if a%b==0) + 1
    return sum(dp.values()) % (10**9+7)

方法四：再尽量简洁的情况下，保证效率，使用OrderedDict保证key的顺序。192ms。

1
2
3
4
5
6
def numFactoredBinaryTrees(self, A: List[int]) -> int:
    dp = OrderedDict()
    for a in sorted(A):
        left = takewhile(lambda x: x <= sqrt(a), dp)
        dp[a] = sum(dp[b] * dp.get(a//b, 0) * (1+(b!=a//b)) for b in left if a%b==0) + 1
    return sum(dp.values()) % (10**9+7)

### 740. Delete and Earn

#### 给定一个整数数组 nums ，你可以对它进行一些操作。每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。返回你能通过这些操作获得的最大点数。

1
2
3
4
5
6
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned


方法一：这题二十分钟AC的。首先将数组分成几个连续的段，再求每段的最大值，和抢房子问题一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def deleteAndEarn(self, nums: List[int]) -> int:

    def max_value_of_seq(ary):
        pick, not_pick = 0, 0
        for num in ary: 
            not_pick, pick = pick, max(not_pick+num*c[num], pick)
        return pick

    parts, c = [], Counter(nums)
    N = len(nums)
    for i, num in enumerate(sorted(set(nums))):
        if not parts or parts[-1][-1]+1!=num:
            parts.append([num])
        else:
            parts[-1].append(num)

    return sum(map(max_value_of_seq, parts)


方法二：看到有大神能用四行写出来，于是我不服。

1
2
3
4
5
def deleteAndEarn(self, nums: List[int]) -> int:
    not_pick, pick, last, c = 0, 0, 0, Counter(nums)
    for a in sorted(set(nums)):
        not_pick, pick, last = pick, max(not_pick+c[a]*a, pick+c[a]*a*(a>last+1)), a
    return pick


### 413. Arithmetic Slices

#### 一个等差数列，至少需要三个数字，每两个挨着的数字差一样。求有多少个连续的等差数列。

1
2
3
A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.


方法一：dp。模拟时间内没做出来是因为忽略了连续。仔细审题后10分钟AC。

1
2
3
4
5
6
def numberOfArithmeticSlices(self, A: List[int]) -> int:
    dp, ans = defaultdict(int), 0
    for i in range(2, len(A)):
        if A[i-2]-A[i-1] == A[i-1]-A[i]:
            dp[i] += dp[i-1] + 1
    return sum(dp.values())


方法二：双指针。

1
2
3
4
5
6
7
8
def numberOfArithmeticSlices(self, A: List[int]) -> int:
    left, right, ans = 0, 2, 0
    while right < len(A):
        while right<len(A) and A[left+1]-A[left]==A[right]-A[right-1]:
            ans += right-left-1
            right += 1
        left = right-1
    return ans


### 1671. Minimum Number of Removals to Make Mountain Array

#### 最少的删除步骤使得变成山峰数组。

1
2
3
Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].


方法一：竞赛时没做出来，想成和941,845题中的思路了。其实是LIS问题，最长上升子序列。这里需要注意一点就是要以当前节点为结尾的最长上升子序列，而不是len(ans)。时间复杂度O(n^2logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
def minimumMountainRemovals(self, nums: List[int]) -> int:
    
    def longest_up(ary):
        ans = []
        for n in ary:
            i = bisect.bisect_left(ans, n)
            ans[i:i+1] = [n]
        return ans.index(ary[-1])
    
    res = 0
    for i in range(1, len(nums)-1):
        res = max(res, longest_up(nums[:i+1])+longest_up(nums[i:][::-1])+1)
    return len(nums) - res

方法二：dp。

### 376. Wiggle Subsequence

#### 最长的摆动序列长度，和LIS最长上升子序列问题一样。

1
2
3
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].


方法一：dp。一开始用了n^2的方法，其实没有必要。

1
2
3
4
5
6
7
8
9
10
11
def wiggleMaxLength(self, nums: List[int]) -> int:
    N = len(nums)
    if N < 2:
        return N
    up = down = 1
    for i in range(1, N):
        if nums[i] > nums[i-1]:
            up = max(up, down+1)
        elif nums[i] < nums[i-1]:
            down = max(down, up+1)
    return max(up, down)


方法二：重复的数字是不需要考虑的。这里做了一次错位。为什么最后一行是or，因为这里对于这个调教a<b>c和a>b<c来说，有一部分重复的比较在里面。

1
2
3
4
5
def wiggleMaxLength(self, nums: List[int]) -> int:
    norep = [num for num, _ in itertools.groupby(nums)]
    if len(norep) < 2: return len(norep)
    triples = list(zip(norep, norep[1:], norep[2:]))
    return 2 + sum(a<b>c or a>b<c for a, b, c in triples)


### 1706. Where Will the Ball Fall

#### 每列的球能落到最下面哪一列，到不了的话返回-1

1
2
3
4
5
6
7
8
Input: grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
Output: [1,-1,-1,-1,-1]
Explanation: This example is shown in the photo.
Ball b0 is dropped at column 0 and falls out of the box at column 1.
Ball b1 is dropped at column 1 and will get stuck in the box between column 2 and 3 and row 1.
Ball b2 is dropped at column 2 and will get stuck on the box between column 2 and 3 and row 0.
Ball b3 is dropped at column 3 and will get stuck on the box between column 2 and 3 and row 0.
Ball b4 is dropped at column 4 and will get stuck on the box between column 2 and 3 and row 1.


方法一：比赛时没做出来，觉得和959很像，所以用并查集去想，结果是不对的。因为并查集可以向上走，而小球只能向下落。

这题应该是dfs或者Dp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findBall(self, grid: List[List[int]]) -> List[int]:
    N = len(grid[0])
    res = [j for j in range(N)]
    for row in grid:
        for j in range(N):
            if res[j] > -1:
                k = res[j]
                if row[k] == 1 and k<N-1 and row[k+1]==1:
                    res[j] += 1
                elif row[k] == -1 and k>0 and row[k-1]==-1:
                    res[j] -= 1
                else:
                    res[j] = -1
    return res


方法二：Lee的方法，如果小球往左或右移动，那么隔板必须是相同的。

1
2
3
4
5
6
7
8
9
10
11
def findBall(self, grid: List[List[int]]) -> List[int]:
    m, n = len(grid), len(grid[0])

    def test(i):
        for j in range(m):
            i2 = i + grid[j][i]
            if i2 < 0 or i2 >= n or grid[j][i2] != grid[j][i]:
                return -1
            i = i2
        return i
    return map(test, range(n))


### 1463. Cherry Pickup II

#### 收集樱桃，每个机器人只能向左下，下，右下移动收集。两个机器人走到同一位置，只能收集一次。



1
2
3
4
5
6
Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.


方法一：dp。dp[i][j1][j2]表示i行，robot1在j1,robot2在j2时的结果。2600ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
def cherryPickup(self, grid: List[List[int]]) -> int:
    # dp[i][j1][j2] 表示i行，robot1在j1, robot2在j2时的结果
    M, N = len(grid), len(grid[0])
    dp = [[[-inf]*(N+2) for _ in range(N+2)] for _ in range(M)]
    dp[0][1][N] = grid[0][0] + grid[0][N-1]
    for i in range(1, M):
        for j1, j2 in product(range(1, N+1), repeat=2):
            for s1, s2 in product([-1, 0, 1], repeat=2):
                dp[i][j1][j2] = max(dp[i][j1][j2], dp[i-1][j1+s1][j2+s2])
            dp[i][j1][j2] += grid[i][j1-1] + grid[i][j2-1] * (j1!=j2)

    # return max(map(max, dp[-1]))
    return max(sum(dp[-1], []))


方法二：记忆化搜索。1000ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def cherryPickup(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])

    @lru_cache(None)
    def dfs(r, c1, c2):
        if r == m: return 0
        cherries = grid[r][c1] + grid[r][c2] * (c1!=c2)
        ans = 0
        for nc1 in range(c1 - 1, c1 + 2):
            for nc2 in range(c2 - 1, c2 + 2):
                if 0 <= nc1 < n and 0 <= nc2 < n:
                    ans = max(ans, dfs(r + 1, nc1, nc2))
        return ans + cherries

    return dfs(0, 0, n - 1)


### 1745. Palindrome Partitioning IV

#### 能否将字符串分为三个回文串。

1
2
3
Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three substrings are palindromes.


方法一：竞赛没时间做，其实比3题简单，亏了。N2时间复杂度可过。只要可以从O(1)时间得到s[i:j]是否是回文串就可以了。

而这个可以通过N2的动态规划来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def checkPartitioning(self, s: str) -> bool:
    N = len(s)
    dp = [[False]*N for _ in range(N)]  # dp[i][j]表示s[i:j+1]是否为回文串
    # 单个字符为回文串
    for i in range(N):
        dp[i][i] = True

    # 预处理, 倒序
    # for i in range(N-2, -1, -1):
    #     for j in range(i+1, N):
    #         if j == i+1:
    #             dp[i][j] = s[i]==s[j]
    #         else:
    #             dp[i][j] = s[i]==s[j] and dp[i+1][j-1] 

    for j in range(1, N):
        for i in range(j-1, -1, -1):
            if i == j-1:
                dp[i][j] = s[i]==s[j]
            else:
                dp[i][j] = s[i]==s[j] and dp[i+1][j-1]

    for i in range(N):
        for j in range(i+1, N):
            if dp[0][i] and dp[i+1][j] and dp[j+1][N-1]:
                return True
    return False


### 1671. Minimum Number of Removals to Make Mountain Array

#### 最少的删除使数组变为山峰数组。

1
2
3
Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].


方法一：和LIS问题一样，找到2个方向的最长上升子序列，然后求和用总数相减，>=2表示既要有上升又要有下降。

1
2
3
4
5
6
7
8
9
10
11
12
def minimumMountainRemovals(self, nums: List[int]) -> int:
    def lis(nums: List[int]):
        n = len(nums)
        dp = [1] * (n)
        for i in range(1, n):
            for j in range(i)[::-1]:
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return dp

    left, right = lis(nums), lis(nums[::-1])[::-1]
    return len(nums) - (max(a+b if a>=2 and b>=2 else 0 for a, b in zip(left, right))-1)


方法二：nlogn的方法。使用二分法。

1
2
3
4
5
6
7
8
9
10
11
def minimumMountainRemovals(self, nums: List[int]) -> int:
    def lis(nums: List[int]):
        dp = [inf] * (len(nums) + 1)
        lens = [0] * len(nums)
        for i, num in enumerate(nums):
            lens[i] = bisect.bisect_left(dp, num) + 1
            dp[lens[i]-1] = num
        return lens

    left, right = lis(nums), lis(nums[::-1])[::-1]
    return len(nums) - (max(a+b if a>=2 and b>=2 else 0 for a, b in zip(left, right))-1)


### 1770. Maximum Score from Performing Multiplication Operations

#### 每次从数组前后拿出一个数和multiplires按序相乘，求累加和最大为多少。

1
2
3
4
5
6
7
Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:
- Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,2], adding 2 * 2 = 4 to the score.
- Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.


方法一：比赛时没有AC，超时了，如果将lru_cache(None)改为lru_cache(M)可以减少耗时。这里LC各个testcase之间是不会清掉cache的，所以有时cache长度过长会导致超时。

1
2
3
4
5
6
7
8
9
10
11
12
def maximumScore(self, nums: List[int], mult: List[int]) -> int:
    M = len(mult)

    @lru_cache(M)
    def dp(idx, i, j):
        if idx == M:
            return 0
        res1 = mult[idx] * nums[i] + dp(idx+1, i+1, j)
        res2 = mult[idx] * nums[j] + dp(idx+1, i, j-1)
        return max(res1, res2)

    return dp(0, 0, len(nums)-1)


方法二：自底向上的方法很难想。

1
2
3
4
5
6
7
8
9
10
def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
    n, m = len(nums), len(multipliers)
    dp = [[0]*m for _ in range(m+1)]

    for i in reversed(range(m)):
        for j in range(i, m): 
            k = i + m - j - 1
            dp[i][j] = max(nums[i] * multipliers[k] + dp[i+1][j], nums[j-m+n] * multipliers[k] + dp[i][j-1])

    return dp[0][-1]


### 1799. Maximize Score After N Operations

#### N步操作的最大分。每次能从数组中选出一对数，次数这两个数的最大公约数累加。

1
2
3
4
Input: nums = [1,2,3,4,5,6]
Output: 14
Explanation: The optimal choice of operations is:
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14


方法一：竞赛没有时间做。记忆化搜索就能过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxScore(self, nums: List[int]) -> int:
    n = len(nums)

    @lru_cache(None)
    def dfs(i, status):
        if i == n//2+1:
            return 0
        cnt = 0
        for j in range(n):
            for k in range(j+1, n):
                new_mask = (1<<j) | (1<<k)
                if not status & new_mask:
                    cnt = max(cnt, i * gcd(nums[j], nums[k]) + dfs(i+1, status | new_mask))
        return cnt

    return dfs(1, 0)


### 1824. Minimum Sideway Jumps

#### 青蛙🐸最小横跳几次能到达终点。



1
2
3
4
Input: obstacles = [0,1,2,3,0]
Output: 2 
Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps (red arrows).
Note that the frog can jump over obstacles only when making side jumps (as shown at point 2).


方法一：比赛时错了一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def minSideJumps(self, obstacles: List[int]) -> int:
    a, b, c = 1, 0, 1
    for i, ob in enumerate(obstacles):
        if ob == 1:
            b = min(b, c+1)
            c = min(c, b+1)
            a = inf
        elif ob == 2:
            a = min(a, c+1)
            c = min(c, a+1)
            b = inf
        elif ob == 3:
            a = min(a, b+1)
            b = min(b, a+1)
            c = inf
        else:
            if i:
                if obstacles[i-1]==1:
                    a = min(b+1, c+1)
                elif obstacles[i-1]==2:
                    b = min(a+1, c+1)
                elif obstacles[i-1]==3:
                    c = min(a+1, b+1)
    return min(a, b, c)


方法二：当前不是障碍时，才能计算min。这里使用取余来简化代码

1
2
3
4
5
6
7
8
9
def minSideJumps(self, A: List[int]) -> int:
    dp = [1, 0, 1]
    for a in A:
        if a:
            dp[a - 1] = float('inf')
        for i in range(3):
            if a != i + 1:
                dp[i] = min(dp[i], dp[(i + 1) % 3] + 1, dp[(i + 2) % 3] + 1)
    return min(dp)


### 1815. Maximum Number of Groups Getting Fresh Donuts

#### 有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前 所有 甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 groups[i] 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。当有一批顾客来到商店时，他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的，那么这一组人都会很开心。你可以随意安排每批顾客到来的顺序。请你返回在此前提下，最多 有多少组人会感到开心。

1
2
3
Input: batchSize = 3, groups = [1,2,3,4,5,6]
Output: 4
Explanation: You can arrange the groups as [6,2,4,5,1,3]. Then the 1st, 2nd, 4th, and 6th groups will be happy.


方法一：此题的动态规划有点难想。这里学到一个新的方法：模拟退火算法，是一种随机算法。因为最后的结果是有顺序的，通过随机交换两个元素，比较结果；如果这个结果是比较优的，那么保留操作。如果较差，则以一定概率保留操作，以跳出局部最优解，从而得到全局最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
    self.res = 0

    RAND_MAX = 2**15

    def calculate():
        cnt = 1
        s = 0
        for i in range(n):
            s = (s+groups[i]) % m
            if s==0 and i!=n-1:
                cnt += 1
        self.res = max(self.res, cnt)
        return cnt

    def simulate_anneal():
        random.shuffle(groups)
        t = 1e6
        while t > 1e-5:
            a, b = randint(0, RAND_MAX) % n, randint(0, RAND_MAX) % n
            x = calculate()
            groups[a], groups[b] = groups[b], groups[a]
            y = calculate()
            delta = y - x
            d = uniform(0, RAND_MAX)
            try:
                c = exp(-delta / t)
            except OverflowError:
                c = float('inf')
            if delta<0 and c>d:
                # 当 y 小于 x 时 , 一定概率 exp(-1 * delta / t) 保留操作
                # 当 y 大于 x 时 ， 就保留交换
                groups[a], groups[b] = groups[b], groups[a]
            t *= 0.985   # 调参，这个值越大，迭代次数越多，越可能超时；这个值越小，迭代次数越少，就可能WA，因为跳不出局部最优解

    mod_zero = sum(g % batchSize==0 for g in groups)
    groups = [g for g in groups if g%batchSize!=0]
    n = len(groups)
    if n == 0:
        return mod_zero
    m = batchSize
    for i in range(20):
        simulate_anneal()
    return self.res + mod_zero


### 474. Ones and Zeroes

#### 最多包含m个0，n个1的最多的子集个数有多少。

1
2
3
4
5
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.


方法一：可以dfs+记忆化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
    N = len(strs)
    self.res = 0

    @lru_cache(None)
    def dfs(m, n, i, cnt):
        if i == N:
            self.res = max(self.res, cnt)
            return
        one, zero = strs[i].count("1"), strs[i].count("0")
        m1, n1 = m-zero, n-one
        if m1 >=0 and n1 >= 0:
            dfs(m1, n1, i+1, cnt+1)
        dfs(m, n, i+1, cnt)

    dfs(m, n, 0, 0)
    return self.res


方法二: 这是一个背包问题。要将原问题转换为「背包问题」，往往需要从题目中抽象出「价值」与「成本」的概念。

这道题如果抽象成「背包问题」的话，应该是：

每个字符串的价值都是 1（对答案的贡献都是 1），选择的成本是该字符串中 1 的数量和 0 的数量。

问我们在 1 的数量不超过 m，0 的数量不超过 n 的条件下，最大价值是多少。

1
2
3
4
5
6
7
8
9
10
11
12
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
    N = len(strs)
    dp = [[[0] * (n+1) for _ in range(m+1)] for _ in range(N+1)]
    for i in range(1, N+1):
        cnt0 = strs[i-1].count("0")
        cnt1 = strs[i-1].count("1")
        for j in range(m+1):
            for k in range(n+1):
                dp[i][j][k] = dp[i-1][j][k]
                if j-cnt0 >= 0 and k-cnt1 >= 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-cnt0][k-cnt1]+1)
    return dp[N][m][n]


方法三：可以倒序，节省一层空间。

1
2
3
4
5
6
7
8
9
10
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
    N = len(strs)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, N+1):
        cnt0 = strs[i-1].count("0")
        cnt1 = strs[i-1].count("1")
        for i in range(m, cnt0 - 1, -1):    #0-1背包问题，内循环逆序
            for j in range(n, cnt1 - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i-cnt0][j-cnt1] + 1)
    return dp[m][n]


### 2369. Check if There is a Valid Partition For The Array

#### 判断数组是否符合要求。

1
2
3
4
Input: nums = [4,4,4,5,6]
Output: true
Explanation: The array can be partitioned into the subarrays [4,4] and [4,5,6].
This partition is valid, so we return true.


方法一： dp，比赛时过了，不过空间需要优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def validPartition(self, nums: List[int]) -> bool:
    N = len(nums)
    dp = [False] * N
    for i in range(1, N):
        if i == 1:
            if nums[i]==nums[i-1]:
                dp[i] = True
        elif i == 2:
            if (nums[i]==nums[i-1]==nums[i-2]) or (nums[i]==nums[i-1]+1==nums[i-2]+2):
                dp[i] = True
        else:
            if not dp[i]:
                if nums[i]==nums[i-1]:
                    dp[i] = dp[i-2]
            if not dp[i]:
                if (nums[i]==nums[i-1]==nums[i-2]) or (nums[i]==nums[i-1]+1==nums[i-2]+2):
                    dp[i] = dp[i-3]
    return dp[-1]


方法二：lee215的写法。因为条件最多用到3个连续元素，所以长度为4的数组就够用了。

1
2
3
4
5
6
7
8
9
10
11
12
def validPartition(self, A: List[int]) -> bool:
    n = len(A)
    dp = [False, False, False, True]
    for i in range(n):
        dp[i % 4] = False
        if i - 1 >= 0 and A[i] == A[i-1]:
            dp[i % 4] |= dp[(i - 2) % 4]
        if i - 2 >= 0 and A[i] == A[i-1] == A[i-2]:
            dp[i % 4] |= dp[(i - 3) % 4]
        if i - 2 >= 0 and A[i] == A[i-1] + 1 == A[i-2] + 2:
            dp[i % 4] |= dp[(i - 3) % 4]
    return dp[(n - 1) % 4]


### 2370. Longest Ideal Subsequence

#### 最长的理想子序列的长度。子序列中小写字母的ascii码小于等于k。

1
2
3
4
Input: s = "acfgbd", k = 2
Output: 4
Explanation: The longest ideal string is "acbd". The length of this string is 4, so 4 is returned.
Note that "acfgbd" is not ideal because 'c' and 'f' have a difference of 3 in alphabet order.


方法一：竞赛时的方法。空间有很大优化空间。时间4000ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def longestIdealString(self, s: str, k: int) -> int:
    def get(c):
        return ord(c)-ord('a')

    N = len(s)
    dp = [[0]*26 for _ in range(N)]
    for i in range(N):
        if i == 0:
            dp[0][get(s[i])] = 1
        else:
            dp[i] = dp[i-1]
            max_d = dp[i][get(s[i])]
            for j in range(max(get(s[i])-k, 0), min(get(s[i])+k+1, 26)):
                max_d = max(max_d, dp[i-1][j]+1, dp[i-1][j])

            dp[i][get(s[i])] = max_d
    return max(dp[-1])


方法二：写法优化，时间600ms。 
1
2
3
4
5
6
def longestIdealString(self, s: str, k: int) -> int:
    dp = [0] * 26 
    for c in s:
        i = ord(c) - ord('a')
        dp[i] = max(dp[max(0, i-k):min(26, i+k+1)]) + 1
    return max(dp)

940. Distinct Subsequences II

一个字符串不同的子序列有多少种。

1
2
3
Input: s = "aba"
Output: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".

方法一：关键点在于，每增加一个字符都可以选择增加到原有的字符上，如果不考虑重复的话，总数为2*n+1，重复的字符串，第二次出现的时候，恰好上该字符上次出现时增加的次数，记作repeat_cnt。

1
2
3
4
5
6
7
8
9
def distinctSubseqII(self, s: str) -> int:
    MOD = 10**9 + 7
    pre_cnt = Counter()
    res = 1
    for c in s:
        add = res
        res = (res + add - pre_cnt[c]) % MOD
        pre_cnt[c] = add
    return res - 1  # 去掉空串

1012. 至少有 1 位重复的数字

给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。

方法一：数位DP，模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def numDupDigitsAtMostN(self, n: int) -> int:
    s = str(n)

    @cache
    def dp(i: int, mask: int, is_limit: bool, is_num: bool) -> int:
        # 从[i:]能够组成无重复数字的个数。
        # mask标记了所有选过的数字集合
        # is_limit 表示前面是否收到了n的约束。若为真，则第i位填入的数字最多为s[i]，否则可以是9.
        # is_num 表示i前面的数位是否填了数字，若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为1；若为真，则要填入的数字可以从0开始。
        if i == len(s):
            return int(is_num) # is_num为True表示得到了一个合法数字
        res = 0
        if not is_num:
            res = dp(i+1, mask, False, False)
        low = 1 - bool(is_num) # 如果前面没有填数字，必须从 1 开始（因为不能有前导零
        up = int(s[i]) if is_limit else 9
        for d in range(low, up+1):
            if (mask >> d & 1) == 0:
                res += dp(i+1, mask | (1<<d), is_limit and d==up, True)
        return res

    return n - dp(0, 0, True, False)