[Programmers] 2 x n 타일링 - 연습문제 (Dynamic Programming)

// 2 x n 타일링 - 연습문제 (Dynamic Programming)
public class Tiling {

	/*
	 * Dynamic Programming은 한 번 해결한 문제는 다시 풀지 않아야하는 방식이다. 메모이제이션을 사용
	 */

	public int solution(int n) { // 피보나치 수열의 규칙을 따른다.
		int[] dp = new int[60001]; // Memoization
		dp[1] = 1;
		dp[2] = 2;

		for (int i = 3; i <= n; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007; // 점화식을 도출하여 풀이
		}
		return dp[n];
	}

}

• Dynamic Programming은 한 번 해결한 문제는 다시 풀지 않아야하는 방식이다. 점화식을 도출하여 메모이제이션 사용

• 타일링 문제 해결법 참고 https://www.youtube.com/watch?v=YHZiWaL49HY&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=22