[14494] 다이나믹이 뭐예요 in python

 

dp는 항상 어렵다 ^^...

 

 

→, ↓의 두 방향으로 움직일 수 있을 때

(1,1)에서 (n,m)까지 도달하는 경우의 수는

dp[x][y]= dp[x-1][y] + dp[x][y-1]

해결할 수도 있다.

 

 

→, ↓, ↘의 세 방향으로 움직일 수 있을 때,

(1,1)에서 (n,m)까지 도달하는 경우의 수는

dp[x][y]= dp[x-1][y] + dp[x][y-1] + dp[x-1][y-1]

위 점화식을 이용하여 구할 수 있다. 

 

즉 갈 수 있는 방향에 따라

더해지는 인수가 달라지는 것을 유의하기

 

 

dp[1][1]에 1을 넣어서 초기화한 후

해당 점화식을 실행시킨다.

 

n=3, m=2이면

0	0	0
0	1	1
0	1	3
0	1	5

 

n, m = map(int, input().split())
dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
dp[1][1] = 1

for x in range(1, n + 1):
    for y in range(1, m + 1):
        if x==1 and y==1:
            continue
        dp[x][y] = dp[x - 1][y] + dp[x - 1][y - 1] + dp[x][y - 1]

print(dp[n][m]%1000000007)