今天的不会 借用大师的答案
※ 引述《DJYOMIYAHINA (通通打死)》之铭言：
: 看着安沙写的 还是没能想到
: dp(i,j) -> s[i:j]的答案
: 每次更新的时候遍历 for k in [i+1,j]
: 若 s[k] = s[i]
: 则可以试着一次打印i:k as s[i]
: 然后加上dp(i,k-1)+dp(k+1,j)
: 因为这时s[i:k-1]以及s[k+1,j]还没有打印好
: 我们只是先决定要打印一排s[i]
: 就根据这个规则遍历下去
: 每次dp(i,j)，就遍历i,j中间的character一次
: 然后稍微memorize一下
: 我其实只会写recursive
: 要我bottom-up我反而完全不会写
: def strangePrinter(self, s: str) -> int:
: n = len(s)
: dp_mem = [[-1 for _ in range(n)] for _ in range(n)]
: #init
: for i in range(n):
: dp_mem[i][i] = 1
: def dp(i,j):
: if j<i:
: return 0
: elif dp_mem[i][j] != -1:
: return dp_mem[i][j]
: cur_dp_val = 1+dp(i+1,j)
: for k in range(i+1,j+1):
: if s[k] == s[i]:
: cur_dp_val = min(cur_dp_val, dp(i,k-1)+dp(k+1,j))
: dp_mem[i][j] = cur_dp_val
: return cur_dp_val
: return dp(0,n-1)
自己的答案就用for循环 但只对了前100个测资 后面100个过不了
class Solution:
def strangePrinter(self, s: str) -> int:
d = defaultdict(list)
# 先找出每个字母所在位置
for i, v in enumerate(s):
d[v].append(i)
word = [' '] * len(s)
current = ans_1 = 0
for _ in range(len(s)):
w = s[_]
if word[_] = s[_]:
continue
idxs = d[w]
curr = []
# 由左至右 画当前位置到每个同字母 所对应的正确字母数
# 原本只找同字母最远的 但不够只好全部都跑一遍
for idx in idxs:
cp = word[:]
cp[_:idx+1] = w * (idx+1-_)
cu = sum(1 for x in range(len(cp)) if cp[x] == s[x])
if cu > current:
curr.append((cu, idx))
# 选最大正确数中最近的idx
current, ix = min(curr, key=lambda x: (-x[0], x[1]))
word[_:ix+1] = cp[_:ix+1]
ans_1 += 1
# 发现反算会得到更少次数 如 tbgtgb 依样照葫芦
word = [' '] * len(s)
current = ans_2 = 0
for _ in range(len(s)-1, -1, -1):
w = s[_]
if word[_] == s[_]:
continue
idxs = d[w][::-1]
curr = []
for idx in idxs:
cp = word[:]
cp[idx:_+1] = w * (_+1-idx)
cu = sum(1 for x in range(len(cp)) if cp[x] == s[x])
if cu > current:
curr.append((cu, idx))
current, ix = min(curr, key=lambda x: (-x[0], x[1]))
word[ix:_+1] = cp[ix:_+1]
ans_2 += 1
return ans_1 if ans_1 < ans_2 else ans_2
其实在一开始自己找测资时就遇到不符合的答案了 但我真不会dp 渍