2775번 dp활용 (python)

https://www.acmicpc.net/problem/2775

정보: 0층은 호수가 인원수 // 각층의 1호는 인원수:1 //

점화식:dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]

3층 1 5 15  35...
2층 1 4 10  20
1층 1 3  6  10 
0층 1 2  3   4

 

시간초과 코드:

N=int(input())

def dp(floor,num):       
    if floor==0:
        return num
    elif num==1:
        return 1
    else:
        return dp(floor,num-1)+dp(floor-1,num)
for i in range(N):
    floor=int(input())
    num=int(input())
    print(dp(floor,num))

 

시간초과 이유: 재귀로 풀다보면  floor와 ho가 클수록 너무 많이 dp함수를 호출하게되어 시간초과가 난다.

 

3층 0 1 5 15  35...
2층 0 1 4 10  20
1층 0 1 3  6  10 
0층 0 1 2  3   4

정답코드:

N=int(input())
dp=[[0]*(15) for _ in range(15)] //0층~14층 0호~14호
for i in range(N):
    floor = int(input())
    ho= int(input())

    for i in range(ho+1 )://0층일때
        dp[0][i]=i
    for i in range(floor):
        for j in range(ho):
            dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]//나머지 호수들   
    print(dp[floor][ho])