我想去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]