Lattice Path

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.

How many such routes are there through a  grid? As number of ways can be very large, print it modulo (10^9 +7)

Constraints 

1 ≤ T ≤ 1000
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 จนผมได้ตารางออกมา

ตอนแรกตารางนี้ไม่ได้มีแถวหรือหลักที่มี 1 แต่เมื่อผมเขียนตาราง 6*6 ออกมาแล้ว วิธีที่ M*N จะทำได้มีค่าเท่ากับ 
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) 

เราสามารถเอาไอเดียนี้เขียนเป็นโค้ดได้ 

	#include <iostream>
	#include <iomanip>
	#include <cstring>
	#include <cmath>
	using namespace std;
	typedef long long ll;
	int main()
	{
	ll P = pow(10.0,9) + 7;
	ll dp[501][501];
	for(int i = 0;i <= 500;i++)
	{
	dp[0][i] = 1;
	dp[i][0] = 1;
	}
	for(int i = 1;i <= 500;i++)
	for(int j = 1;j <= 500;j++)
	dp[i][j] = ((dp[i-1][j]%P) + (dp[i][j-1]%P))%P;
	int tc;
	cin >> tc;
	while(tc--)
	{
	int n,m;
	cin >> n >> m;
	cout << dp[n][m] << endl;
	}
	}

view raw Project Euler 015.cpp hosted with ❤ by GitHub

สามารถไปลองทำกันได้ที่ www.hackerrank.com