dynamic programming 4

* 틀린 내용이 있을 시 지적 부탁드립니다.

문제는 더블릿 21 dynamic programming에 있는 partition입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/partition/partition.php?pname=partition

문제에 나와있는 것 처럼 특정 수의 분할 수를 구하는것이 목표입니다.

dp배열을 행을 특정 수, 열을 그 가짓수로 만들 수 있는 특정 수의 개수라고 했을 때 나열해보면

1    2    3    4    5    6    7    8   

1    1    0    0    0    0    0    0    0

2    1    1    0    0    0    0    0    0

3    1    1    1    0    0    0    0    0

4    1    2    1    1    0    0    0    0    

5    1    2    2    1    1    0    0    0    

6    1    3    3    2    1    1    0    0    

7    1    3    4    3    2    1    1    0

8    1    4    5    5    3    2    1    1

이렇게 됩니다.

여기서 규칙을 찾아보면 dp[행][열]의 값은 dp[행-1][열-1]+dp[행-열][열]인 것을 알 수 있습니다.

dp[8][2]=dp[7][1]+dp[6][2]

입력받은 수까지 돌리고 마지막 행의 값을 모두 더해서 출력해주면 됩니다.