a=2000
b=2000
if b>a:
a, b = b, a
d=[]
for i in range(a):
d[i:]=[[]]
if i>=b:
x = b
else:
x = i
for j in range(x+1):
if (i == 0) and (j == 0):
d[i][j:] = [0]
elif (i == 0) or (j == 0):
d[i][j:] = [1]
elif i == j:
d[i][j:] = [d[i][j-1]*2]
else:
d[i][j:] = [d[i][j-1] + d[i-1][j]]
if i>0:
d[i-1]=[]
print d[a-1][b-1]ผลการรัน โดยใช้ time จับเวลา
415828425864924998634542842325676808706232957586556725463361909680781449739748170
786476583991009842613588566821101566552449812050519515271426829403308897930154848
139000401217874574325171349240478804805012554662232593418186105627855887297242750
191258293109799452562416018445296661723328582808673234975864811354576092306731674
226129026615041968499816993517068588780940662630054770440825519413455865220243087
597454080782838938422451159980693138755678460019308423353936671267937407109197183
261946634690754460222691463521097187455850580048349711806796515481309363032514472
631419167126959879296426641287728281408263950661584874428072352076560611103304329
056994774368533971570942013663930927771345889508878174490486498112868394435125871
368770117617083125252317200772612121394477978635381281677951466408518108004063757
181565789433577065739615351320655283808516684687687348436814782925229015434783262
936635458985024720378317210338353260437300968307371995465273889042991687076670199
592582593447226951517354719649532201876810233809966157181452417833096317816478439
040563226541144136090250318325435743209975329838676879857054480550574759550296644
05427578211111064192312240045083183062752759630345186798202023360000
real 0m6.381s
user 0m5.024s
sys 0m0.076s
ลองแก้ขนาดเป็น 4000x4000 คำตอบยาวมากไม่โพสต์แล้วกัน แต่จับเวลาได้
real 0m59.338s
user 0m27.342s
sys 0m0.148s
ทั้งหมดรันบนแล็ปท็อป AMD Turion64 2.2GHz (1 core), RAM 1GB
ไม่มีความคิดเห็น :
แสดงความคิดเห็น