7296 : 메모이제이션 계단
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 계단이 있을 때, 한 번에 최대 $K$개의 계단을 오를 수 있다면 꼭대기에 도달하는 방법의 수를 구하십시오.
메모이제이션(Top-down DP)으로 구현해야 합니다.
점화식: $dp[n] = \sum_{j=1}^{K} dp[n-j]$
[제약 조건]
• 입력되는 모든 수는 정수입니다.
메모이제이션(Top-down DP)으로 구현해야 합니다.
점화식: $dp[n] = \sum_{j=1}^{K} dp[n-j]$
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 계단 수 $N$과 최대 계단 수 $K$가 주어집니다. ($1 \le N \le 100$, $1 \le K \le 10$)
출력 설명
꼭대기에 도달하는 방법의 수를 $10^9+7$로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8도움
memo = {}; def dp(n): if n in memo: return memo[n]; if n==0: return 1; memo[n]=sum(dp(n-j) for j in range(1,K+1) if n>=j)%MOD; return memo[n]