JustAnOtherClone
Senior Member
câu 3 input có 200 tưởng brute force được cơ mà vẫn dính tle, thôi nghỉ sớm vậy.
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
MOD = 10**9 + 7
@lru_cache(None)
def dp(zeroCount, oneCount, zeroRemaining, oneRemaining):
if zeroRemaining == 0 and oneRemaining == 0:
return 1
if zeroRemaining < 0 or oneRemaining < 0:
return 0
ans = 0
if zeroCount + oneCount > limit and zeroCount > 0 and oneCount > 0:
ans = dp(0, 0, zeroRemaining, oneRemaining)
else:
ans = dp(zeroCount + 1, oneCount, zeroRemaining - 1, oneRemaining) + dp(zeroCount, oneCount + 1, zeroRemaining, oneRemaining - 1)
return ans % MOD
return dp(0, 0, zero, one)
nay e làm chay ko xài ide, câu 1 thì bỏ biến đếm nhầm chỗ, chạy tay hơn chục lần đúng r mà sao báo wrong hoài.Đm nó làm câu 1 submit sai 1 lần ạ thiếu mẹ cái if tốn thời gian quá
Hợp lý nhể, dp['i'][j][0/1] là số dãy độ dài i, có j phần tử bằng 0 và kết thúc bằng 0/1. (i-j) = số lương phần tử 1 trong mảng rồi.ý tưởng dp cho q3 với q4 nó là xét f[j][0] và f[j][1]
ý nghĩa là số lượng dãy độ dài i, có j số bằng 0 (hoặc 1) và kết thúc bằng 0 và 1
em cũng làm giống các bố top đầu nhưng cài hàm dp bị sai sml
hic em mới chơi voz không quen cú phápHợp lý nhể, dp['i'][j][0/1] là số dãy độ dài i, có j phần tử bằng 0 và kết thúc bằng 0/1. (i-j) = số lương phần tử 1 trong mảng rồi.
Sao em lại đâm đầu giải bài này theo math
Đúng hơn là cái hint là tuần này câu khó phải giải bằng dp, vì daily tuần này là dp