การปีนบันไดและการจัดเหรียญ
สร้างความสัมพันธ์เวียนเกิดแบบหนึ่งมิติคลาสสิกตั้งแต่ต้น
การปีนบันไดและการจัดเหรียญ เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
มารู้จักปัญหาการขึ้นบันได
คุณสามารถก้าวครั้งละ 1 หรือ 2 ขั้นได้ จะมีวิธีไปถึงขั้นที่ n กี่วิธี ปัญหา 1D DP สุดคลาสสิกนี้ก็คือฟีโบนัชชีในรูปแบบอื่น
ค้นหาความสัมพันธ์เวียนเกิด
หากต้องการอยู่บนขั้นที่ i คุณต้องมาจากขั้นที่ i-1 หรือ i-2 ดังนั้น dp[i] = dp[i-1] + dp[i-2] ซึ่งเป็นการรวมการก้าวครั้งล่าสุดทั้งสองแบบ
dp[i] = dp[i-1] + dp[i-2]ตั้งกรณีฐาน
มีหนึ่งวิธีในการอยู่ที่พื้น และมีหนึ่งวิธีในการไปถึงขั้นที่ 1 กรณี ฐาน เหล่านี้จะเป็นจุดเริ่มต้นของตารางทั้งหมด
dp[0], dp[1] = 1, 1เติมตารางและอ่านคำตอบ
วนขึ้นไปตามลำดับ แล้วช่องสุดท้ายจะเก็บจำนวนวิธีไว้ คำตอบทั้งหมดเป็นเพียงรอบการ เติมตาราง ขนาดเล็ก
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]ลดเหลือตัวแปรสองตัว
คุณต้องใช้เพียงค่าสองค่าล่าสุด จึงไม่จำเป็นต้องใช้อาร์เรย์ เวอร์ชันที่ใช้ หน่วยความจำ O(1) นี้เป็นที่นิยมในการแข่งขัน
a, b = 1, 1
for _ in range(n):
a, b = b, a+bเปลี่ยนไปนับชุดเหรียญ
เมื่อกำหนดค่าเหรียญมาให้ ให้นับจำนวนวิธีสร้างจำนวนเงิน A ในที่นี้ลำดับไม่สำคัญ เราจึงนับ ชุดผสม ไม่ใช่ลำดับ
coins = [1, 2, 5]ตารางชุดผสม
ให้ dp[x] เป็นจำนวนวิธีสร้าง x เริ่มจากหนึ่งวิธีในการสร้างศูนย์ ซึ่งก็คือ เซตว่างของเหรียญ
dp = [0]*(A+1)
dp[0] = 1วางรอบเหรียญไว้ด้านนอก
วาง รอบวนซ้ำของเหรียญไว้นอกรอบจำนวนเงิน ลำดับนี้จะนับแต่ละชุดผสมเพียงครั้งเดียว และไม่เกิดการนับการเรียงสับเปลี่ยน
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]ชุดผสมกับการเรียงสับเปลี่ยน
หากสลับลำดับรอบวนซ้ำ คุณจะนับ วิธีที่มีลำดับ แทน เพียงการซ้อนรอบวนซ้ำต่างกันก็เปลี่ยนความหมายของคำตอบได้
รูปแบบหาจำนวนเหรียญน้อยที่สุด
หากต้องการหาเหรียญจำนวนน้อยที่สุด ให้เก็บค่าต่ำสุดแทนผลรวม ตั้งต้นด้วย อนันต์ แล้วเลือกหนึ่งบวกกับคำตอบที่ดีที่สุดของปัญหาย่อย
dp[x] = min(dp[x], dp[x-c] + 1)รูปแบบเดียว ประยุกต์ได้หลายแบบ
บันไดและเหรียญมีโครงสร้างร่วมกัน: แต่ละสถานะจะรวมค่าหรือเลือกค่าต่ำสุดจาก สถานะก่อนหน้า ไม่กี่สถานะ เมื่อมองเห็นรูปแบบนี้ การเขียนโค้ดก็ตรงไปตรงมา
ตรวจสอบอย่างรวดเร็ว
ในการนับชุดผสมของเหรียญ ลำดับรอบวนซ้ำแบบใดช่วยหลีกเลี่ยงการนับซ้ำ
ทบทวน: รวมการก้าวครั้งล่าสุด
ตอนนี้คุณสามารถแก้ปัญหาบันไดและการนับเหรียญด้วย ความสัมพันธ์เวียนเกิดแบบ 1D ได้แล้ว คำตอบแต่ละค่าจะรวมจากสถานะก่อนหน้าไม่กี่สถานะ และลำดับรอบวนซ้ำจะเป็นตัวกำหนดว่าจะได้ชุดผสมหรือการเรียงสับเปลี่ยน
คำถามที่พบบ่อย
บทเรียน “การปีนบันไดและการจัดเหรียญ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การปีนบันไดและการจัดเหรียญ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ 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 ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “การปีนบันไดและการจัดเหรียญ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การจดจำผลลัพธ์เทียบกับการทำตาราง
- กำหนดสถานะและการเปลี่ยนสถานะ
- การปีนบันไดและการจัดเหรียญ
- ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด