Má nó mình chủ quan ko dùng cái template là for j in range(i, n) ở trong DP mà set nó thành dp(prevIndex, index) rồi tính frequency ở bên ngoài vì nghĩ là time complexity là như nhau.
Sol Q2 của em:câu 2 brute force TLE, hôm bữa bác nào bên thớt daily xúi Q1, Q2 auto bruteforce nghe theo lừa vl
Em phát hiện ra rồi, khai báo bool label[26] = {false} thì submit mới đúng. Tưởng default array thì tất cả phần từ phải false chứ nhỉ
câu này đề đọc sao e làm v luôn. tìm hình vuông bé thứ 2 chứa tag trùng r đếm xem bao nhiêu điểm nằm bên trong đó
Nếu em nhớ không nhầm thì 1 biến hay mảng được khai báo global mà không gán giá trị gì thì mới nhận giá trị mặc định. Còn nếu được khai báo bên trong hàm thì sẽ nhận 1 giá trị tuỳ ý nào đó (thực ra không hẳn là tuỳ ý
).Uk, em mới check thì thấy bảo tùy bộ compiler và setup môi trường nữa. Nên thôi rút kinh nghiệm chuyển sang dùng vector.Nếu em nhớ không nhầm thì 1 biến hay mảng được khai báo global mà không gán giá trị gì thì mới nhận giá trị mặc định. Còn nếu được khai báo bên trong hàm thì sẽ nhận 1 giá trị tuỳ ý nào đó (thực ra không hẳn là tuỳ ý
can be non-standard and may cause unexpected issues, especially with standard library containers and iterators. Instead of using a C-style array, you can use std::vector<bool> for better compatibility and behavior:
đm lần sau ko sáng tạo DP nữa mà xài template có sẵn thôi, ngồi sáng tạo ra cái frequency check loay hoay cả tiếng éo biết tại sao lại TLE 
class Solution:
def minimumSubstringsInPartition(self, s: str) -> int:
n = len(s)
frequencyCheck = [[False] * n for _ in range(n)]
for i in range(len(s)):
frequency = defaultdict(int)
frequency[s[i]] += 1
frequencyCheck[i][i] = True
for j in range(i + 1, len(s)):
frequency[s[j]] += 1
if len(set(frequency.values())) == 1:
frequencyCheck[i][j] = True
@lru_cache(None)
def dp(prev_index, index):
if index == len(s) - 1:
if frequencyCheck[prev_index][index]:
return 1
else:
return float('inf')
ans = float('inf')
if frequencyCheck[prev_index][index]:
ans = min(ans, 1 + dp(index + 1, index + 1))
ans = min(ans, dp(prev_index, index + 1))
return ans
return dp(0, 0)
class Solution:
def minimumSubstringsInPartition(self, s: str) -> int:
@cache
def dp(end):
if end < 0:
return 0
ans = math.inf
counter = Counter()
eqMax = 0
maxCnt = 0
for l in range(end, -1, -1):
counter[s[l]] += 1
if counter[s[l]] == maxCnt:
eqMax += 1
elif counter[s[l]] > maxCnt:
maxCnt = counter[s[l]]
eqMax = 1
if eqMax == len(counter):
ans = min(ans, 1 + dp(l - 1))
return ans
n = len(s)
return dp(n - 1)
Câu đó t cũng không có ý tưởng gì, chắc bỏ thôiKhông có ý tưởng gì cho câu 4 luôn
bạn có thể backtracking và có stop early cho scoreKhông có ý tưởng gì cho câu 4 luôn
bạn cho mình tham khảo code với
.
