การจดจำผลลัพธ์เทียบกับการทำตาราง
สองวิธีสำหรับแคชคำตอบของโจทย์ย่อย
การจดจำผลลัพธ์เทียบกับการทำตาราง เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
เหตุใดจึงต้องแคช
การเรียกซ้ำแบบพื้นฐานทำงานเดิมซ้ำแล้วซ้ำอีก การเขียนโปรแกรมพลวัตจะเก็บคำตอบของแต่ละกรณีไว้เพียงครั้งเดียว จึงไม่ต้องคำนวณซ้ำ
fib(40) # slow: recomputes endlesslyปัญหาย่อยที่ซ้อนทับกัน
DP เหมาะกับปัญหาที่แบ่งออกเป็นปัญหาย่อยที่ซ้อนทับกัน กรณีเล็ก ๆ เดิมจะปรากฏซ้ำในหลายแขนงของการเรียกซ้ำ
fib(5) needs fib(3) twiceจากบนลงล่าง: การจดจำผลลัพธ์
การจดจำผลลัพธ์คือการเรียกซ้ำธรรมดาที่เพิ่มแคช คุณคำนวณเมื่อจำเป็นและจดจำผลลัพธ์ตั้งแต่ครั้งแรกที่พบข้อมูลนำเข้าแต่ละแบบ
memo = {}การจดจำผลลัพธ์อย่างง่ายในไพธอน
ตัวตกแต่ง lru_cacheเปลี่ยนการเรียกซ้ำที่ช้าให้เป็น DP ที่รวดเร็วด้วยบรรทัดเดียว โดยแคชการเรียกทุกครั้งโดยอัตโนมัติ
from functools import lru_cache
@lru_cache(None)
def f(n): ...จากล่างขึ้นบน: การทำตาราง
การทำตารางเติมตารางจากกรณีที่เล็กที่สุดขึ้นไปจนถึงคำตอบ โดยใช้ลูปแทนการเรียกซ้ำ
dp = [0] * (n + 1)ฟีโบนัชชีแบบทำตาราง
กำหนดค่าฐานก่อน แล้วให้แต่ละช่องอ่านค่าที่คำนวณไว้แล้ว ไม่มีสแตกการเรียก ใช้เพียงลูปที่เป็นระเบียบ
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]คำตอบเดียวกัน รูปแบบต่างกัน
การจดจำผลลัพธ์และการทำตารางแก้สมการเวียนเกิดเดียวกัน ต่างกันเพียงทิศทาง คือจากบนลงล่างตามความต้องการ หรือจากล่างขึ้นบนตามลำดับ
เมื่อใดควรเลือกการจดจำผลลัพธ์
เลือกใช้การจดจำผลลัพธ์เมื่อเขียนสมการเวียนเกิดในรูปแบบการเรียกซ้ำได้เป็นธรรมชาติ และคุณอาจไม่จำเป็นต้องคำนวณทุกสถานะ
เมื่อใดควรเลือกการทำตาราง
เลือกการทำตารางสำหรับลูปที่ต้องทำงานแน่นหนา เพื่อหลีกเลี่ยงข้อผิดพลาดจากขีดจำกัดการเรียกซ้ำ และเมื่อคุณจะคำนวณทั้งตารางอยู่แล้ว
import sys; sys.setrecursionlimit(10**6)ระวังขีดจำกัดการเรียกซ้ำ
การเรียกซ้ำที่จดจำผลลัพธ์และมีความลึกมากอาจชนขีดจำกัดการเรียกซ้ำของไพธอน และทำงานล้มเหลวด้วยผลลัพธ์ข้อผิดพลาดขณะทำงานเมื่อข้อมูลนำเข้ามีขนาดใหญ่
ทั้งสองวิธีมีต้นทุนเดียวกัน
ไม่ว่าจะใช้วิธีใด ความเร็วที่เพิ่มขึ้นมาจากการแก้แต่ละสถานะเพียงครั้งเดียว เวลารวมเท่ากับจำนวนสถานะคูณด้วยงานที่ทำต่อสถานะ
ตรวจสอบสั้น ๆ
วิธีใดเติมตารางจากล่างขึ้นบนด้วยลูป
ทบทวน: สองเส้นทาง DP เดียวกัน
ตอนนี้คุณสามารถแคชปัญหาย่อยได้สองวิธี การจดจำผลลัพธ์ใช้การเรียกซ้ำจากบนลงล่าง ส่วนการทำตารางใช้ลูปจากล่างขึ้นบน เลือกวิธีที่อ่านเข้าใจง่ายกว่า ✨
คำถามที่พบบ่อย
บทเรียน “การจดจำผลลัพธ์เทียบกับการทำตาราง” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การจดจำผลลัพธ์เทียบกับการทำตาราง” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การจดจำผลลัพธ์เทียบกับการทำตาราง”
สองวิธีสำหรับแคชคำตอบของโจทย์ย่อย คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “การจดจำผลลัพธ์เทียบกับการทำตาราง” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การจดจำผลลัพธ์เทียบกับการทำตาราง
- กำหนดสถานะและการเปลี่ยนสถานะ
- การปีนบันไดและการจัดเหรียญ
- ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด