Algorithms training - Linear DP. 算法训练(三) 线性DP.

我嘅理解: 线性DP就是用 for 循环实现的 dp, 不依赖于任何嘅数据结构.

https://leetcode.cn/problems/extra-characters-in-a-string/

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        n = len(s)
        d = set(dictionary)
        f = [0] * (n + 1) # f[i] 表示 [0, i - 1] 嘅结果

        for i in range(1, n + 1):
            f[i] = f[i - 1] + 1 # 唔选
            for j in range(1, i + 1): # 睇下前面选边个
                if s[j - 1 : i] in d:
                    f[i] = min(f[i], f[j - 1])
        return f[n]

https://leetcode.cn/problems/find-the-substring-with-maximum-cost/

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        n = len(s)
        mapping = dict(zip(chars, vals))
        f = [0] * (n + 1)
        for i in range(1, n + 1):
            a = mapping.get(s[i - 1], ord(s[i - 1]) - ord('a') + 1)
            f[i] = a # 唔接力
            f[i] = max(f[i], max(f[i - 1], 0) + a) # 接力
        
        return max(f) # 注意系整个数组的最大值

2547. Minimum Cost to Split an Array

https://leetcode.cn/problems/minimum-cost-to-split-an-array/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import Counter

class Solution:
    def minCost(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [0x3f3f3f3f for i in range(0, n+1)]
        f[0] = 0

        for i in range(1, n+1):
            cnt = Counter()
            s = 0
            for j in range(i - 1, -1, -1):
                cnt[nums[j]] += 1
                if (cnt[nums[j]] == 2):
                    s += 2
                elif cnt[nums[j]] > 2:
                    s += 1
                f[i] = min(f[i], f[j] + k + s)

        return f[n]