https://www.acmicpc.net/problem/1010
강 서쪽에 n개의 지점, 강 동쪽에 m개의 지점이 있을 때 n개의 다리를 지으려고 한다. (n <= m)
중요한 것은 이때 다리가 겹치면 안된다는 것이다.
dp 문제는 그림을 그려야 눈에 확 들어오는 것 같다.
우선 가장 위에 고정선을 그어주고, 그 이외의 다른 점들끼리 이어질 수 있는 경우의 수를 생각해보았다.
n = 2, m = 4
인 (2)번의 경우, 가장 위의 점을 고정선으로 두었을 때 n = 1, m = 3
인 (1)번이 보이는 것을 확인할 수 있다. (; 연두색 영역)
따라서 점화식은 다음과 같이 생각할 수 있다.
dp[n][m] = dp[n-1][m-1] + dp[n-1][m-2] + ... + dp[n-1][n-1]
import sys
input = sys.stdin.readline
# 다리는 겹치면 안된다.
def bridge(n,m):
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(1,m+1):
dp[1][i] = i
for j in range(2,n+1):
for k in range(j,m+1):
for l in range(k,j-1,-1):
dp[j][k] += dp[j-1][l-1]
return dp[n][m]
T = int(input().rstrip())
for _ in range(T):
n, m = map(int,input().rstrip().rsplit())
print(bridge(n,m))