[알고리즘] 합분해 (DP-GoldⅤ)

목적 :

dp 테이블 손으로 써서 푸는 습관을 들이기 위해서

​

문제 설명(요약) :

0~N까지의 숫자 중 K개를 택해서 택한 숫자의 합이 N이 되는 경우의 수를 구하기

조건 -> 중복 허용, 숫자 위치만 바꾼 것은 다른 경우로 count

​

해결 전략:

1. 머리로 풀다가 이차원 dp형태로 풀어야 겠다 싶어 손으로 풀기 시작

2. 1~6까지의 경우의 수를 직접 구해봄 (조합,순열)

3. 피보나치 수열 인줄 알았는데 단순 대각선 합이였음

4. 점화식 세움

5. 끝

​

직접 그려본 dp 테이블 :

점화식 :

dp[i][j] = dp[i-1][j] + dp[i][j-1]

​