Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
Constraints
1 ≤ T ≤ 1000
1 ≤ N ≤ 500
1 ≤ M ≤ 500
1 ≤ N ≤ 500
1 ≤ M ≤ 500
โจทย์ข้อนี้ต้องการให้เราหาว่า ถ้าเราเริ่มจากจุดบนสุดฝั่งซ้ายลงจุดล่างสุดฝั่งขวา จะทำได้กี่วิธี ซึ่งถ้าดูแล้วเป็นโจทย์ที่ดูค่อนข้างจะง่าย เพราะสามารถใช้เรื่อง combinatorics เข้ามาแก้ได้ (N+M)!/(N!M!)
แต่ว่า N กับ M อาจจะเป็นได้ถึง 500 ซึ่งค่าเยอะมาก ผมเลยไม่ได้ใช้สูตรนี้เข้ามาแก้ เมื่อผมลองมองหาวิธีอื่น ผมก็นึกถึง dynamic programming ผมเลยลองคิดว่าถ้าสี่เหลี่ยมขนาด 1*1 จะมีได้กี่วิธี และถ้า 2*1 จะมีได้กี่วิธี ผมลองเพิ่มหลักไปเรื่อยๆจนเป็น 1*6 แล้วลองเพิ่มแถวเป็น 2*1 3*1 ... 6*1 จนผมได้ตารางออกมา
สามารถไปลองทำกันได้ที่ www.hackerrank.com
แต่ว่า N กับ M อาจจะเป็นได้ถึง 500 ซึ่งค่าเยอะมาก ผมเลยไม่ได้ใช้สูตรนี้เข้ามาแก้ เมื่อผมลองมองหาวิธีอื่น ผมก็นึกถึง dynamic programming ผมเลยลองคิดว่าถ้าสี่เหลี่ยมขนาด 1*1 จะมีได้กี่วิธี และถ้า 2*1 จะมีได้กี่วิธี ผมลองเพิ่มหลักไปเรื่อยๆจนเป็น 1*6 แล้วลองเพิ่มแถวเป็น 2*1 3*1 ... 6*1 จนผมได้ตารางออกมา
ตอนแรกตารางนี้ไม่ได้มีแถวหรือหลักที่มี 1 แต่เมื่อผมเขียนตาราง 6*6 ออกมาแล้ว วิธีที่ M*N จะทำได้มีค่าเท่ากับ
DP[i][j] = DP[i-1][j] + DP[i][j-1] เช่นถ้าผมอยากรู้ว่า 1*1 ทำได้กี่วิธี
DP[i][j] = DP[i-1][j] + DP[i][j-1] เช่นถ้าผมอยากรู้ว่า 1*1 ทำได้กี่วิธี
ผมสามารถหาได้จาก DP[1][1] = DP[0][1] + DP[1][0] , DP[0][1] = 1 DP[1][0] = 1 DP[1][1] จึงเท่ากับ 2 แต่ว่าโจทย์ข้อนี้เราต้องระวังเพราะเขาต้องการให้เรา mod(10^9+7) เพราะฉะนั้นในการสร้างตารางเราจะต้องทำการ mod ไม่ให้ค่าเกิน 10^9 +7
( (a+b)%m = (a%m + b%m)%m)
เราสามารถเอาไอเดียนี้เขียนเป็นโค้ดได้
ไม่มีความคิดเห็น:
แสดงความคิดเห็น