수 분할

//수분할 자연수n을 순서에 상관없이 하나 이상의 자연수의 합으로 나타내는 방법 //3의 경우 1+1+1 / 2+1 2가지 방법이 있다 // 5/2수분할 1+1+1+1+1 / 2+1+1+1 / 2+2+1 3가지 // 5/3수분할 1+1+1+1+1 / 2+1+1+1 / 2+2+1 / 3+1+1 / 3+2 5가지 int partition(int n, int m) { int iCnt = 0, i; if(n < m) m = n; if(n==0) return 1; for(i = 1 ; i <=m ; ++i) iCnt += partition(n-i, i); return iCnt; } //메모제이션 int partition_memo(int n, int m) { static int memo[200][200]; int iCnt = 0, i; if(n<m) m+n; if(memo[n][m] > 0) return memo[n][m]; if(n ==0) return memo[n][m] = 1; for(i = 1 ; i <- m; ++i) iCnt += partition_memo(n - i , i); return memo[n][m] = iCnt; }