我想去s
哀
:(
第二题
改的简单一点了
dp[0] 目前遍历过的array中 只取一个的最大分数 (a[0]*b[i0])
dp[1] 目前遍历过的array中 只取两个的最大分数 (a[0]*b[i0]+a[1]*b[i1])
dp[2] 目前遍历过的array中 只取三个的最大分数 (a[0]*b[i0]+a[1]*b[i1]+a[2]*b[i2])
dp[3] 目前遍历过的array中 取四个的最大分数 (a[0]*b[i0]+a[1]*b[i1]+a[2]*b[i2]+
a[3]*b[i3])
当visit到新的element的时候
dp[3]会是max of
1. 还没看到这个element之前取四个的最大值
2. 还没看到这个element之前取三个的最大值+a[3]*b_cur
dp[2],d[1],dp[0]就依此类推
从3做到0 因为dependency
def maxScore(self, a: List[int], b: List[int]) -> int:
dp = [-10**9 for _ in range(len(a))]
# you can't init as 0 here
for num in b:
dp[3] = max(dp[3], dp[2]+a[3]*num)
dp[2] = max(dp[2], dp[1]+a[2]*num)
dp[1] = max(dp[1], dp[0]+a[1]*num)
dp[0] = max(dp[0], a[0]*num)
return dp[3]
第三题
我一开始用trie+dfs 直接TLE
然后想说 是不是不用trie
就整个打掉改用DP重写 结果还是TLE
最后其实是DP+trie 我没有把两个加在一起
简单来说就是
for i = [0:n]
每个loop都往后检查target[i:j] for j = [i:n]
检查的方式是用trie
当j慢慢往前的时候
查target[i:j]就不用一直重新做O(len(word))的检查 只要node往前就好
有在prefix字典内的话 就更新dp value
class Node:
def __init__(self):
self.child = [None for _ in range(26)]
class Solution:
def minValidStrings(self, words: List[str], target: str) -> int:
# construct dict
root = Node()
for word in words:
cur = root
for c in word:
if cur.child[ord(c)-ord('a')] is None:
cur.child[ord(c)-ord('a')] = Node()
cur = cur.child[ord(c)-ord('a')]
dp = [10**9 for _ in range(len(target))]
dp.append(0) # dp[-1] = 0
for i in range(len(target)):
cur = root
for j in range(i,len(target)):
if cur.child[ord(target[j])-ord('a')] is not None:
cur = cur.child[ord(target[j])-ord('a')]
dp[j] = min(dp[j], dp[i-1]+1)
else:
break
return -1 if dp[len(target)-1] == 10**9 else dp[len(target)-1]